BuildCircuit | Topcoder Archive

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 R₁,R₂,...,R_n combined in serial. The resistance is equal to R₁+R₂+...+R_n. Or
several circuits R₁,R₂,...,R_n combined in parallel. The resistance is equal to 1/((1/R₁)+(1/R₂)+...+(1/R_n)).

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

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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.