Statistics

Problem Statement for "MaximizeValue"

Problem Statement

A castle has N > 1 rooms, numbered 0 to N-1.

A knight can attempt to collect gold from the castle. At the beginning of the attempt, exactly x gold coins are placed into room x, for all x. To start the attempt, the knight must choose a single non-negative integer S smaller than N. This number S will remain constant during the entire attempt.

The only door to the castle leads to room 1. The knight can use this door to enter the castle and start the attempt. At any point when in room 1, the knight can also use the door to end the attempt and leave the castle.

Whenever in a room number x, the knight has two options:

  • Collect all gold coins from this room.
  • Move to the room number (x*S) modulo N.

Given is a prime number P > 2 and a positive integer K. The number N of rooms in the castle is 2*(PK). In words: N is twice the value of P to the power of K.

Help the knight: for the given N find and return any choice of S that can be used to maximize the amount of coins with which the knight can leave the castle.

Definition

Class:
MaximizeValue
Method:
solve
Parameters:
long, int
Returns:
long
Method signature:
long solve(long P, int K)
(be sure your method is public)

Notes

  • During an attempt the coins in each room can only be collected once. Once the knight collects them, the room is now empty for the rest of the attempt.

Constraints

  • P will be at least 3.
  • P will be a prime number.
  • K will be at least 1.
  • N = 2*P^K will not exceed 10^14.

Examples

  1. 3

    1

    Returns: 5

    We have N = 2*(3^1) = 2*3 = 6. For S = 5 the knight can enter the castle, start the attempt in room 1, go to room 5, collect the 5 coins there, go to room (5*5) mod 6 = 1, collect the 1 coin there, and leave the castle with 5+1 = 6 coins. For S = 1 the knight has the option to go from room 1 to room 1, but that clearly does not help. The knight can only collect the 1 gold coin in room 1. For any other S the knight can only enter the castle, pick up the one coin from room 1 and leave immediately. Any attempt to move to a different room leads to a situation in which the knight remains stuck in the castle forever. The knight may collect more coins (for S = 2 the knight can collect 1+2+4 = 7 coins), but that does not count as the knight is unable to bring those 7 coins out of the castle. Hence, the correct return value is 5.

  2. 7

    2

    Returns: 47

    Here N = 2 * 7^2 = 98. The choice S = 47 allows the knight to leave the castle with 2058 gold coins. No other choice of S is better. Several other choices of S lead to the same outcome as S = 47. These would also be accepted as correct answers.

  3. 999999937

    1

    Returns: 392783989

  4. 7071061

    2

    Returns: 6352677

  5. 3

    28

    Returns: 22876792454963

  6. 49999999999981

    1

    Returns: 83846554145933

  7. 49999999999919

    1

    Returns: 33280440123559

  8. 49999999999711

    1

    Returns: 93974241839509

  9. 49999999999421

    1

    Returns: 75093179340925

  10. 29666407

    1

    Returns: 34465439

  11. 962569

    2

    Returns: 926539505499

  12. 8535864768917

    1

    Returns: 1776377755645

  13. 658199

    2

    Returns: 433226109361

  14. 203311

    2

    Returns: 41335508903

  15. 53

    7

    Returns: 39

  16. 19

    10

    Returns: 6131066257803

  17. 1142357

    2

    Returns: 1304980468987

  18. 71777

    2

    Returns: 5151940423

  19. 1997351

    2

    Returns: 587141

  20. 6062061542567

    1

    Returns: 2652207232193

  21. 153991

    2

    Returns: 23713320529

  22. 35107

    3

    Returns: 43269428370901

  23. 3079

    3

    Returns: 29189662279

  24. 1743433

    2

    Returns: 272729

  25. 3180319846637

    1

    Returns: 5927560709467

  26. 103

    6

    Returns: 1194052296675

  27. 234482325179

    1

    Returns: 295779061523

  28. 211

    5

    Returns: 141

  29. 499

    5

    Returns: 30938747502585

  30. 7589

    3

    Returns: 5761

  31. 1025611

    2

    Returns: 1051878774173

  32. 1768523

    2

    Returns: 3127675031517

  33. 101917

    2

    Returns: 10387133061

  34. 151

    6

    Returns: 11853911588407

  35. 167

    6

    Returns: 21691961596529

  36. 89603

    2

    Returns: 20639

  37. 2262078073

    1

    Returns: 2303168083

  38. 181913

    2

    Returns: 33092515439

  39. 3

    28

    Returns: 22876792454963

  40. 1213

    4

    Returns: 2164926734623

  41. 54700320713

    1

    Returns: 95189920137

  42. 3

    28

    Returns: 22876792454963

  43. 34843729

    1

    Returns: 55452375

  44. 1423

    4

    Returns: 665

  45. 401

    5

    Returns: 31

  46. 3

    28

    Returns: 22876792454963

  47. 15833487850139

    1

    Returns: 23538276101445

  48. 23

    10

    Returns: 41426511213669

  49. 11994090207991

    1

    Returns: 15921536411549

  50. 709

    4

    Returns: 653

  51. 904940093

    1

    Returns: 470135307

  52. 34770563017

    1

    Returns: 22935455561

  53. 152484653

    1

    Returns: 59371601

  54. 7817

    3

    Returns: 477661608213

  55. 88547

    2

    Returns: 7840592321

  56. 269

    5

    Returns: 1408514752789

  57. 17638850891

    1

    Returns: 24750942905

  58. 651221

    2

    Returns: 424089060549

  59. 8053478227097

    1

    Returns: 13281761614967

  60. 19193912447

    1

    Returns: 14504203359

  61. 293

    5

    Returns: 2159424884907

  62. 7

    16

    Returns: 5

  63. 24107

    3

    Returns: 10917

  64. 99643

    2

    Returns: 15697

  65. 5184337141231

    1

    Returns: 229934094325

  66. 823663

    2

    Returns: 437337

  67. 1594173839221

    1

    Returns: 491603651625

  68. 31657

    3

    Returns: 16621

  69. 425443980889

    1

    Returns: 276174545505

  70. 18749

    3

    Returns: 13047

  71. 14691343

    1

    Returns: 19472533

  72. 4903

    3

    Returns: 117865226869

  73. 24564768023

    1

    Returns: 6168867285

  74. 41179

    2

    Returns: 27597

  75. 26921

    3

    Returns: 9477

  76. 11

    13

    Returns: 34522712143933

  77. 47

    8

    Returns: 13

  78. 22079

    3

    Returns: 5507

  79. 237941269

    1

    Returns: 162500331

  80. 19

    10

    Returns: 15

  81. 4327

    3

    Returns: 81014117717

  82. 62315377897

    1

    Returns: 89910150517

  83. 7323711097

    1

    Returns: 1028474745

  84. 103

    6

    Returns: 45

  85. 1877

    4

    Returns: 809

  86. 77933

    2

    Returns: 35559

  87. 51613

    2

    Returns: 2663932367

  88. 137

    6

    Returns: 6611856250723

  89. 7

    16

    Returns: 5

  90. 17408881695757

    1

    Returns: 19240741482481

  91. 103963

    2

    Returns: 10808315379

  92. 14410093

    1

    Returns: 12429195

  93. 60414517

    1

    Returns: 115538089

  94. 261569699029

    1

    Returns: 485955260403

  95. 1419691242253

    1

    Returns: 683768439979

  96. 16903

    3

    Returns: 4829379956897

  97. 8487649

    1

    Returns: 1324393

  98. 619397

    2

    Returns: 383653028369

  99. 3889

    3

    Returns: 58818485793

  100. 6553447

    2

    Returns: 42947668006767

  101. 1256693

    2

    Returns: 1579278415753

  102. 2251

    4

    Returns: 2167

  103. 19507

    3

    Returns: 7422863134527

  104. 1303

    4

    Returns: 701

  105. 3059803

    2

    Returns: 1910217

  106. 5

    19

    Returns: 3

  107. 47017

    2

    Returns: 2210599967

  108. 3

    28

    Returns: 22876792454963

  109. 294781

    2

    Returns: 86895944367

  110. 97

    2

    Returns: 57

  111. 181

    4

    Returns: 171

  112. 467

    4

    Returns: 47562812223

  113. 1291

    1

    Returns: 1363

  114. 191

    3

    Returns: 127

  115. 59

    5

    Returns: 714924337

  116. 103

    3

    Returns: 1092797

  117. 3839203

    1

    Returns: 919481

  118. 59473

    1

    Returns: 116785

  119. 1969831

    1

    Returns: 2492887

  120. 6705911

    1

    Returns: 176143

  121. 354139

    1

    Returns: 360339

  122. 115301

    1

    Returns: 222439

  123. 751

    2

    Returns: 564311

  124. 64661

    1

    Returns: 29661

  125. 103333

    1

    Returns: 171355

  126. 22193

    2

    Returns: 492545503

  127. 503

    3

    Returns: 127263935

  128. 7

    6

    Returns: 3

  129. 1938719

    1

    Returns: 1418597

  130. 78017

    1

    Returns: 141267

  131. 971

    3

    Returns: 915498899

  132. 189743

    1

    Returns: 252681

  133. 666599

    1

    Returns: 607679

  134. 1009

    2

    Returns: 971

  135. 1032617

    1

    Returns: 1828093

  136. 6973579

    1

    Returns: 6956155

  137. 5972297

    1

    Returns: 11605977

  138. 5

    12

    Returns: 3

  139. 773999

    1

    Returns: 773797

  140. 49999999998589

    1

    Returns: 63317280066401

  141. 43

    3

    Returns: 79519

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: