Statistics

Problem Statement for "Tigerrymander"

Problem Statement

To celebrate the Lunar New Year that starts the Year of the Tiger, the problems in this set feature tigers.


Absurdistan has always been famous for having a population of oxen and tigers living peacefully together. However, recently there has been an issue of contention: how to celebrate the Lunar New Year? The tigers want huge fireworks while the oxen consider it a waste of money. As always, the final decision will be decided by a referendum: a nation-wide vote.


The tigers really want the fireworks, so they decided to help their issue by cunningly manipulating the voting system. Instead of simply counting all the votes, they will divide the country into several exactly equally large districts. Each district will take its own vote on the issue and then it will nominate one delegate (either a tiger or an ox) to represent the opinion that won in the district. Those delegates will then cast the votes that will determine the final outcome of the referendum.

And the tigers are not required to stop at one level of hierarchy. For the next step, each district can now be divided into sub-districts. The sub-districts must again have exactly the same size, all over the country, so that everything seems as fair as possible. Each sub-district will take a vote and nominate one sub-delegate for the district vote, and then each district will evaluate the votes of those sub-delegates and nominate one delegate for the country vote.

Obviously, the above process can be continued recursively arbitrarily many times. Again, we emphasize that on each level of the election hierarchy all sub*-districts across the whole country must have exactly the same size.


One final peculiarity of the voting system in Absurdistan is that a tiger is TV / OV times more powerful than an ox, and therefore a tiger's vote is worth TV and an ox's vote is worth OV.

As tigers are the ones who want change, they must have a strict majority in order for the motion to pass. (If in some vote the total weight of the tigers' votes is the same as the total weight of the votes of the oxen, an ox is nominated as the delegate.)


The total population of Absurdistan is N. Assume that tigers have perfect control over how to divide the country into districts - they get to choose the depth of the hierarchy, the district sizes, and they also decide which inhabitants belong into which districts. Calculate and return the minimal number of tigers in the population needed to get the fireworks.

Definition

Class:
Tigerrymander
Method:
minTigers
Parameters:
long, int, int
Returns:
long
Method signature:
long minTigers(long N, int TV, int OV)
(be sure your method is public)

Constraints

  • N will be between 1 and 5 * 10^12, inclusive.
  • TV will be between 1 and 10, inclusive.
  • OV will be between 1 and 10, inclusive.

Examples

  1. 4

    1

    1

    Returns: 3

    There are 4 animals in Absurdistan, and the votes of tigers and oxen count the same. The tigers could divide the country into four districts of size 1, but that's the same as not dividing it at all: each district would simply nominate its only member. The tigers could also divide the country into two districts of size 2. This isn't exactly helpful: whenever there are two votes, both voters must be tigers in order for the tigers' motion to win. And thus if there are two districts of size 2, the tigers will only get fireworks if all four animals are tigers. Perhaps surprisingly, the best strategy here is to have everyone vote in the same election. Then three tigers can already outvote one ox.

  2. 13

    2

    1

    Returns: 5

    Again, the optimal solution is that there are no districts. Four tigers are not yet enough to win against nine oxen, but five tigers already have a stronger total vote than eight oxen.

  3. 12

    7

    7

    Returns: 6

    If everyone voted together, at least seven tigers would be needed. However, six tigers can still win the referendum by splitting the country cleverly. Using T and O to represent tigers and oxen, one optimal solution is to form four districts: TTO, TTO, TTO and OOO. Three districts will nominate a tiger while only one will nominate an ox, so in the final vote the tigers win 3:1. (There is one other solution that also allows six tigers to win the election.)

  4. 28

    3

    1

    Returns: 2

    Yes, you read that correctly, two tigers who cleverly manipulate the system can win the whole election here.

  5. 21

    1

    10

    Returns: 20

  6. 1

    1

    1

    Returns: 1

  7. 1

    6

    2

    Returns: 1

  8. 2

    1

    1

    Returns: 2

  9. 2

    7

    9

    Returns: 2

  10. 3

    1

    1

    Returns: 2

  11. 3

    8

    10

    Returns: 2

  12. 4

    1

    1

    Returns: 3

  13. 4

    6

    5

    Returns: 1

  14. 5

    1

    1

    Returns: 3

  15. 5

    9

    7

    Returns: 3

  16. 6

    1

    1

    Returns: 4

  17. 6

    7

    10

    Returns: 4

  18. 7

    1

    1

    Returns: 4

  19. 7

    1

    7

    Returns: 7

  20. 8

    1

    1

    Returns: 5

  21. 8

    1

    2

    Returns: 6

  22. 9

    1

    1

    Returns: 4

  23. 9

    1

    5

    Returns: 8

  24. 10

    1

    1

    Returns: 6

  25. 10

    8

    9

    Returns: 6

  26. 11

    1

    1

    Returns: 6

  27. 11

    1

    6

    Returns: 10

  28. 12

    1

    1

    Returns: 6

  29. 12

    10

    7

    Returns: 2

  30. 13

    1

    1

    Returns: 7

  31. 13

    4

    4

    Returns: 7

  32. 14

    1

    1

    Returns: 8

  33. 14

    9

    9

    Returns: 8

  34. 15

    1

    1

    Returns: 6

  35. 15

    6

    8

    Returns: 6

  36. 16

    1

    1

    Returns: 9

  37. 16

    4

    1

    Returns: 1

  38. 17

    1

    1

    Returns: 9

  39. 17

    9

    6

    Returns: 7

  40. 18

    1

    1

    Returns: 8

  41. 18

    6

    10

    Returns: 8

  42. 19

    1

    1

    Returns: 10

  43. 19

    6

    9

    Returns: 12

  44. 20

    1

    1

    Returns: 9

  45. 20

    10

    4

    Returns: 2

  46. 21

    1

    1

    Returns: 8

  47. 21

    4

    1

    Returns: 2

  48. 22

    1

    1

    Returns: 12

  49. 22

    3

    6

    Returns: 15

  50. 23

    1

    1

    Returns: 12

  51. 23

    2

    6

    Returns: 18

  52. 24

    1

    1

    Returns: 10

  53. 24

    10

    7

    Returns: 2

  54. 25

    1

    1

    Returns: 9

  55. 25

    9

    9

    Returns: 9

  56. 26

    1

    1

    Returns: 14

  57. 26

    5

    2

    Returns: 4

  58. 27

    1

    1

    Returns: 8

  59. 27

    4

    6

    Returns: 8

  60. 28

    1

    1

    Returns: 12

  61. 28

    4

    8

    Returns: 15

  62. 29

    1

    1

    Returns: 15

  63. 29

    2

    7

    Returns: 23

  64. 30

    1

    1

    Returns: 12

  65. 30

    10

    6

    Returns: 4

  66. 31

    1

    1

    Returns: 16

  67. 31

    5

    4

    Returns: 14

  68. 32

    1

    1

    Returns: 15

  69. 32

    9

    5

    Returns: 1

  70. 33

    1

    1

    Returns: 12

  71. 33

    6

    9

    Returns: 14

  72. 34

    1

    1

    Returns: 18

  73. 34

    10

    1

    Returns: 2

  74. 35

    1

    1

    Returns: 12

  75. 35

    8

    5

    Returns: 6

  76. 36

    1

    1

    Returns: 12

  77. 36

    10

    7

    Returns: 4

  78. 37

    1

    1

    Returns: 19

  79. 37

    5

    9

    Returns: 24

  80. 38

    1

    1

    Returns: 20

  81. 38

    4

    10

    Returns: 28

  82. 39

    1

    1

    Returns: 14

  83. 39

    2

    4

    Returns: 27

  84. 40

    1

    1

    Returns: 15

  85. 40

    7

    8

    Returns: 15

  86. 53662

    7

    8

    Returns: 16356

  87. 589056

    5

    6

    Returns: 39600

  88. 1022400

    7

    7

    Returns: 32400

  89. 2124084

    7

    6

    Returns: 163392

  90. 5831070

    7

    6

    Returns: 307584

  91. 7765740

    4

    7

    Returns: 568512

  92. 7867000

    6

    9

    Returns: 1510720

  93. 8454624

    9

    4

    Returns: 27099

  94. 8685936

    2

    3

    Returns: 665100

  95. 9921808

    1

    1

    Returns: 1502613

  96. 11288538

    3

    8

    Returns: 2918475

  97. 11883416

    7

    7

    Returns: 1916720

  98. 18367392

    10

    7

    Returns: 68160

  99. 18422580

    7

    6

    Returns: 217728

  100. 27970584

    5

    5

    Returns: 3067000

  101. 28516704

    8

    7

    Returns: 277246

  102. 34301120

    9

    6

    Returns: 55134

  103. 82672896

    7

    9

    Returns: 9082800

  104. 83771088

    7

    1

    Returns: 218154

  105. 98722688

    6

    10

    Returns: 16296228

  106. 100889728

    6

    9

    Returns: 12788190

  107. 112185024

    2

    10

    Returns: 61351332

  108. 156196608

    5

    10

    Returns: 32947803

  109. 302819328

    1

    3

    Returns: 81842475

  110. 569423232

    7

    10

    Returns: 22109400

  111. 628172800

    10

    3

    Returns: 11328

  112. 636146688

    8

    6

    Returns: 177498

  113. 666575360

    1

    7

    Returns: 414404991

  114. 846027264

    3

    2

    Returns: 176970

  115. 1266701312

    4

    10

    Returns: 214710183

  116. 1835039232

    1

    10

    Returns: 1173788935

  117. 4453904384

    3

    10

    Returns: 1837671862

  118. 4620512256

    6

    3

    Returns: 1002716

  119. 6815465472

    8

    8

    Returns: 259991250

  120. 8840294400

    5

    2

    Returns: 14100

  121. 10676264960

    4

    5

    Returns: 488723625

  122. 10720370688

    1

    5

    Returns: 4273394125

  123. 12151474176

    5

    6

    Returns: 809091750

  124. 14627438592

    7

    5

    Returns: 12300

  125. 15828172800

    9

    6

    Returns: 42210

  126. 16936218624

    2

    4

    Returns: 932678955

  127. 26233569280

    1

    10

    Returns: 18176929875

  128. 29374980096

    10

    7

    Returns: 34560

  129. 40363643520

    1

    4

    Returns: 11782638000

  130. 53731360768

    10

    9

    Returns: 776725

  131. 63132647424

    10

    1

    Returns: 434

  132. 65081737216

    9

    6

    Returns: 794455

  133. 117766356992

    4

    9

    Returns: 6121708245

  134. 123245756416

    3

    3

    Returns: 5289136875

  135. 127814664192

    4

    2

    Returns: 433400

  136. 135050463602

    10

    1

    Returns: 57769980

  137. 148406665216

    10

    9

    Returns: 255013

  138. 158156437553

    1

    9

    Returns: 115529027328

  139. 234453073920

    7

    4

    Returns: 66720

  140. 246253223936

    5

    10

    Returns: 10965714228

  141. 366207155757

    3

    2

    Returns: 11574663936

  142. 396240041543

    3

    8

    Returns: 210898711861

  143. 439977938400

    2

    8

    Returns: 52390800000

  144. 539929972207

    1

    1

    Returns: 135287194050

  145. 610840084480

    7

    5

    Returns: 121932

  146. 642507465600

    1

    1

    Returns: 587865600

  147. 656476128534

    1

    8

    Returns: 522109669483

  148. 863837650962

    1

    5

    Returns: 330291561600

  149. 894702483567

    6

    1

    Returns: 4733875575

  150. 898910720836

    9

    6

    Returns: 35967593888

  151. 905976981479

    6

    5

    Returns: 187191953492

  152. 917192429149

    1

    8

    Returns: 724870344160

  153. 930246454160

    1

    1

    Returns: 78493543128

  154. 950872948546

    1

    10

    Returns: 715519308591

  155. 1009116466889

    10

    1

    Returns: 8355730635

  156. 1042794676224

    1

    6

    Returns: 286200486936

  157. 1053659234304

    9

    4

    Returns: 42578

  158. 1076544828635

    9

    1

    Returns: 21530896573

  159. 1076879831137

    9

    7

    Returns: 98394272120

  160. 1093424809205

    2

    3

    Returns: 190577154144

  161. 1351478673408

    8

    10

    Returns: 15028875000

  162. 1466005953063

    1

    1

    Returns: 122316555150

  163. 1479680568748

    1

    1

    Returns: 554880213282

  164. 1480188493824

    8

    8

    Returns: 14749218750

  165. 1606268664000

    9

    4

    Returns: 138240

  166. 1617878913351

    1

    8

    Returns: 1278330318846

  167. 1670519410560

    5

    1

    Returns: 1728

  168. 1711025316000

    2

    3

    Returns: 7096320000

  169. 1799020903680

    1

    1

    Returns: 1306368000

  170. 1927522396800

    7

    8

    Returns: 1556755200

  171. 2137076602101

    7

    1

    Returns: 23749947

  172. 2248776129600

    2

    1

    Returns: 1935360

  173. 2318302247853

    1

    2

    Returns: 1030384127704

  174. 2330482714938

    8

    2

    Returns: 7398357826

  175. 2336782634030

    1

    1

    Returns: 94771826856

  176. 2545945382114

    1

    1

    Returns: 324170308800

  177. 2654245887419

    7

    1

    Returns: 5925611730

  178. 2658965241938

    3

    1

    Returns: 24453251635

  179. 2786526943200

    1

    1

    Returns: 1306368000

  180. 2808194427352

    1

    3

    Returns: 1382161548075

  181. 2891283595200

    7

    1

    Returns: 108

  182. 2891283595200

    8

    4

    Returns: 2580480

  183. 2974451444279

    1

    1

    Returns: 427773458100

  184. 2983402795373

    10

    1

    Returns: 1083789956

  185. 3029052236172

    2

    1

    Returns: 56378298900

  186. 3140019277565

    3

    9

    Returns: 1884011566540

  187. 3168982531120

    8

    10

    Returns: 194019338880

  188. 3212537328000

    1

    1

    Returns: 1763596800

  189. 3212537328000

    1

    9

    Returns: 1377496834560

  190. 3212537328000

    10

    1

    Returns: 48

  191. 3212537328000

    10

    4

    Returns: 80640

  192. 3292325996836

    2

    5

    Returns: 1348746994530

  193. 3373164194400

    1

    1

    Returns: 1567641600

  194. 3373164194400

    5

    7

    Returns: 5080320000

  195. 3373164194400

    8

    4

    Returns: 3870720

  196. 3448539676197

    2

    2

    Returns: 159239927424

  197. 3457551757423

    1

    8

    Returns: 2450844824064

  198. 3464273851136

    1

    1

    Returns: 289978280100

  199. 3597760450556

    2

    4

    Returns: 545713425180

  200. 3747348352499

    1

    7

    Returns: 2869209671328

  201. 3748406830777

    1

    1

    Returns: 269301545920

  202. 3914001609231

    5

    5

    Returns: 187065038160

  203. 4040150908193

    2

    1

    Returns: 157814625930

  204. 4062684692965

    10

    1

    Returns: 73866994418

  205. 4220150196398

    1

    1

    Returns: 2110075098200

  206. 4265237242999

    2

    1

    Returns: 160650956880

  207. 4291433687432

    1

    1

    Returns: 170558196480

  208. 4302525256987

    8

    6

    Returns: 790629817040

  209. 4310879103756

    10

    1

    Returns: 1209562039

  210. 4315272922693

    9

    8

    Returns: 213101190888

  211. 4323154990605

    1

    3

    Returns: 1475551126300

  212. 4463376323439

    1

    1

    Returns: 204954592752

  213. 4470935674380

    1

    1

    Returns: 101972535552

  214. 4497552259200

    1

    1

    Returns: 2351462400

  215. 4497552259200

    1

    10

    Returns: 2033637838848

  216. 4497552259200

    2

    5

    Returns: 131736084480

  217. 4497552259200

    9

    6

    Returns: 10886400

  218. 4500005363403

    1

    1

    Returns: 209357575680

  219. 4614493549680

    9

    1

    Returns: 1078520

  220. 4706141764326

    1

    5

    Returns: 2742334719117

  221. 4726514093172

    8

    1

    Returns: 541488480

  222. 4746052164079

    1

    1

    Returns: 1186581665610

  223. 4818805992000

    1

    1

    Returns: 1959552000

  224. 4930463781687

    6

    1

    Returns: 37071156255

  225. 4958340418274

    5

    10

    Returns: 2203721132530

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: