TopCoder problem "BuildCircuit" used in SRM 390 (Division I Level Three)



Problem Statement

    A serial-parallel resistor circuit is either
  1. a single resistor. The resistance of such circuit is equal to the resistance of the resistor. Or
  2. several circuits R1,R2,...,Rn combined in serial. The resistance is equal to R1+R2+...+Rn. Or
  3. several circuits R1,R2,...,Rn combined in parallel. The resistance is equal to 1/((1/R1)+(1/R2)+...+(1/Rn)).

Given two positive integers a and b, your task is to build a serial-parallel resistor circuit that has resistance equal to a/b. You are only allowed to use two kinds of resistors: R=1 and R=2. Return the minimal number of resistors needed. If the circuit cannot be built with 16 or less resistors, return -1.

 

Definition

    
Class:BuildCircuit
Method:minimalCount
Parameters:int, int
Returns:int
Method signature:int minimalCount(int a, int b)
(be sure your method is public)
    
 

Constraints

-a and b will each be between 1 and 50000, inclusive.
 

Examples

0)
    
1
1
Returns: 1
One unit resistor is enough.
1)
    
2
3
Returns: 2
Combine R=1 and R=2 in parallel.
2)
    
6
5
Returns: 3
Combine R=1 and R=2 in serial, then with R=2 in parallel.
3)
    
42
47
Returns: 7
4)
    
1
20
Returns: -1
5)
    
756
874
Returns: 10

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8510

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8510

Writer:

srbga

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Brute Force, Math