Statistics

Problem Statement for "BuildCircuit"

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

  1. 1

    1

    Returns: 1

    One unit resistor is enough.

  2. 2

    3

    Returns: 2

    Combine R=1 and R=2 in parallel.

  3. 6

    5

    Returns: 3

    Combine R=1 and R=2 in serial, then with R=2 in parallel.

  4. 42

    47

    Returns: 7

  5. 1

    20

    Returns: -1

  6. 756

    874

    Returns: 10

  7. 2902

    1198

    Returns: 12

  8. 6123

    4328

    Returns: 15

  9. 4401

    4622

    Returns: 15

  10. 867

    6703

    Returns: -1

  11. 9243

    8878

    Returns: 16

  12. 9951

    3251

    Returns: 16

  13. 5831

    9127

    Returns: 16

  14. 15874

    3005

    Returns: 16

  15. 33110

    46621

    Returns: -1

  16. 48536

    13004

    Returns: 16

  17. 156

    16

    Returns: 8

  18. 284

    1491

    Returns: 7

  19. 28

    7

    Returns: 2

  20. 16816

    32339

    Returns: -1

  21. 50000

    50000

    Returns: 1

  22. 6

    2

    Returns: 2

  23. 9

    10

    Returns: 5

  24. 4

    8

    Returns: 2

  25. 7

    4

    Returns: 4

  26. 8

    9

    Returns: 5

  27. 7

    9

    Returns: 5

  28. 10

    3

    Returns: 4

  29. 2

    9

    Returns: 5

  30. 10

    2

    Returns: 3

  31. 8

    9

    Returns: 5

  32. 108

    87

    Returns: 6

  33. 178

    69

    Returns: 8

  34. 91

    149

    Returns: 10

  35. 17

    7

    Returns: 5

  36. 77

    195

    Returns: 10

  37. 181

    42

    Returns: 9

  38. 93

    113

    Returns: 9

  39. 69

    85

    Returns: 9

  40. 174

    45

    Returns: 6

  41. 183

    55

    Returns: 9

  42. 155

    110

    Returns: 6

  43. 183

    116

    Returns: 9

  44. 86

    145

    Returns: 10

  45. 82

    148

    Returns: 8

  46. 73

    75

    Returns: 10

  47. 155

    136

    Returns: 9

  48. 81

    125

    Returns: 9

  49. 96

    84

    Returns: 4

  50. 90

    14

    Returns: 7

  51. 37

    20

    Returns: 7

  52. 997

    1625

    Returns: 13

  53. 1825

    615

    Returns: 10

  54. 2893

    622

    Returns: 14

  55. 1917

    2240

    Returns: 13

  56. 1859

    1418

    Returns: 14

  57. 1921

    2211

    Returns: 14

  58. 1721

    2140

    Returns: 14

  59. 1549

    296

    Returns: 13

  60. 233

    2937

    Returns: -1

  61. 635

    2341

    Returns: 15

  62. 520

    1156

    Returns: 10

  63. 2955

    866

    Returns: 14

  64. 1107

    2411

    Returns: 14

  65. 777

    2078

    Returns: 14

  66. 2549

    1029

    Returns: 13

  67. 1284

    2223

    Returns: 12

  68. 1285

    901

    Returns: 12

  69. 2887

    2164

    Returns: 14

  70. 804

    1051

    Returns: 12

  71. 1992

    460

    Returns: 10

  72. 2781

    2757

    Returns: 13

  73. 1798

    1909

    Returns: 13

  74. 2461

    375

    Returns: 13

  75. 1480

    2442

    Returns: 6

  76. 1906

    1420

    Returns: 12

  77. 953

    858

    Returns: 13

  78. 1536

    1231

    Returns: 13

  79. 79

    553

    Returns: 7

  80. 110

    1571

    Returns: -1

  81. 1682

    1205

    Returns: 13

  82. 44800

    26355

    Returns: 13

  83. 47546

    13255

    Returns: -1

  84. 43405

    18878

    Returns: -1

  85. 39249

    35028

    Returns: 13

  86. 24784

    24363

    Returns: -1

  87. 31159

    2712

    Returns: -1

  88. 2596

    6158

    Returns: 13

  89. 17613

    25382

    Returns: -1

  90. 46433

    9821

    Returns: -1

  91. 11874

    21960

    Returns: 15

  92. 3832

    16626

    Returns: 16

  93. 38681

    34214

    Returns: -1

  94. 24505

    42825

    Returns: -1

  95. 23190

    29013

    Returns: 16

  96. 36290

    11061

    Returns: -1

  97. 46486

    17419

    Returns: -1

  98. 49565

    49459

    Returns: -1

  99. 16574

    25138

    Returns: -1

  100. 47212

    36950

    Returns: 16

  101. 43822

    41804

    Returns: -1

  102. 28275

    20358

    Returns: 7

  103. 38775

    14665

    Returns: 15

  104. 49035

    8416

    Returns: -1

  105. 39338

    26470

    Returns: -1

  106. 32675

    3818

    Returns: -1

  107. 34316

    36434

    Returns: 16

  108. 11233

    10577

    Returns: -1

  109. 6838

    46382

    Returns: -1

  110. 5031

    34017

    Returns: -1

  111. 39864

    49153

    Returns: -1

  112. 39472

    27344

    Returns: 14

  113. 24141

    40037

    Returns: -1

  114. 25225

    21687

    Returns: -1

  115. 3306

    7265

    Returns: 15

  116. 33212

    33470

    Returns: -1

  117. 6384

    32996

    Returns: 16

  118. 34792

    15987

    Returns: -1

  119. 28562

    41323

    Returns: -1

  120. 40237

    38775

    Returns: -1

  121. 15504

    21247

    Returns: 16

  122. 20154

    25762

    Returns: 16

  123. 49270

    13246

    Returns: 16

  124. 2791

    1482

    Returns: 14

  125. 49993

    49999

    Returns: -1

  126. 756

    888

    Returns: 8

  127. 7282

    995

    Returns: 14

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.
This problem was used for: