BuildCircuit
SRM 390 · 2008-02-02 · by srbga
SRM 390 · 2008-02-02 · by srbga · Brute Force, Math
Problem Statement
Problem Statement
A serial-parallel resistor circuit is either
- a single resistor. The resistance of such circuit is equal to the resistance of the resistor. Or
- several circuits R1,R2,...,Rn combined in serial. The resistance is equal to R1+R2+...+Rn. Or
- 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.
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
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BuildCircuit with a public method int minimalCount(int a, int b) · 127 test cases · 2 s / 256 MB per case