Statistics

Problem Statement for "PrimeCompositeGame"

Problem Statement

You and Mr. Dengklek are playing a game called Prime-Composite Game.

Initially, there is a pile consisting of N stones. You and Mr. Dengklek take alternating turns, starting from you. In your turn, you must remove at least 1 and at most K stones from the pile. Additionally, after your move the number of stones in the pile must be a prime number. In Mr. Dengklek's turn, he must remove at least 1 and at most K stones from the pile. Additionally, after his move the number of stones in the pile must be a composite number. The first player who cannot make a valid move loses the game.

You and Mr. Dengklek both play the game optimally. Optimal play is defined as follows: Clearly, one of the players has a strategy that will guarantee him winning the game. If at any turn this player has multiple moves to choose from, he always chooses the one that minimizes the number of turns the game will take. The other player always chooses the move that will maximize the number of turns the game will take. Each player is following these rules and each player knows that the other player is also following these rules.

You are given the ints N and K. Determine the outcome of the game. Let X be the number of turns in the game. If you win, return X, otherwise return -X.

Definition

Class:
PrimeCompositeGame
Method:
theOutcome
Parameters:
int, int
Returns:
int
Method signature:
int theOutcome(int N, int K)
(be sure your method is public)

Notes

  • A prime number is a positive number that has exactly two distinct divisors. A composite number is a positive number that has more than two distinct divisors. By definition, 1 is neither prime nor composite.

Constraints

  • N will be between 1 and 474,747, inclusive.
  • K will be between 1 and N, inclusive.

Examples

  1. 3

    2

    Returns: 1

    Take a single stone in your first turn, leaving two stones. This ends the game, as Mr. Dengklek now has no valid move.

  2. 58

    1

    Returns: 0

    The game is already over and you lost, as you have no valid move to make. (The only option is to take a single stone, but 57 is not a prime number.)

  3. 30

    3

    Returns: -2

    The game will proceed as follows: You will take 1 stone, leaving 29 stones. Mr. Dengklek will take 1 or 2 stones, leaving 28 or 27 stones. In either case, you cannot leave a prime number of stones in your next turn, therefore, you will surely lose.

  4. 6

    3

    Returns: 1

    Taking 1 stone in your first turn would guarantee you to win after your next turn. However, it is better to take 3 stones and win right now.

  5. 526

    58

    Returns: 19

  6. 2

    1

    Returns: 0

  7. 2

    2

    Returns: 0

  8. 3

    1

    Returns: 1

  9. 3

    2

    Returns: 1

  10. 3

    3

    Returns: 1

  11. 8

    2

    Returns: 5

  12. 14

    2

    Returns: -4

  13. 24

    3

    Returns: 13

  14. 90

    5

    Returns: 35

  15. 114

    3

    Returns: -8

  16. 117

    7

    Returns: 37

  17. 474747

    1

    Returns: 0

  18. 474747

    5

    Returns: 0

  19. 474747

    474747

    Returns: 1

  20. 474747

    213

    Returns: 4625

  21. 31416

    58

    Returns: 1227

  22. 89654

    58

    Returns: -1416

  23. 265562

    77

    Returns: -2526

  24. 155971

    77

    Returns: 4431

  25. 403433

    319728

    Returns: 3

  26. 464843

    169867

    Returns: 5

  27. 239679

    35554

    Returns: 13

  28. 304124

    288946

    Returns: 3

  29. 430212

    290442

    Returns: 3

  30. 455587

    284499

    Returns: 3

  31. 202679

    158631

    Returns: 3

  32. 102314

    58652

    Returns: 3

  33. 344099

    236800

    Returns: 3

  34. 391145

    5240

    Returns: 149

  35. 274888

    190935

    Returns: 3

  36. 284564

    174745

    Returns: 3

  37. 421780

    109226

    Returns: 7

  38. 213614

    149869

    Returns: 3

  39. 172682

    124409

    Returns: 3

  40. 283867

    246625

    Returns: 3

  41. 298788

    22160

    Returns: 27

  42. 205938

    175422

    Returns: 3

  43. 175893

    39043

    Returns: 9

  44. 50674

    28052

    Returns: 3

  45. 473319

    74785

    Returns: 13

  46. 415420

    36371

    Returns: 23

  47. 156227

    10982

    Returns: 29

  48. 316638

    23938

    Returns: 27

  49. 447248

    41244

    Returns: 21

  50. 31416

    58

    Returns: 1227

  51. 39897

    123

    Returns: 683

  52. 474160

    1000

    Returns: 959

  53. 370297

    97

    Returns: 8317

  54. 474747

    9997

    Returns: 95

  55. 442119

    111

    Returns: 8569

  56. 370297

    97

    Returns: 8317

  57. 370318

    100

    Returns: 8135

  58. 22190

    18

    Returns: -50

  59. 461718

    71

    Returns: -1394

  60. 468

    9

    Returns: -24

  61. 58832

    42

    Returns: -422

  62. 1

    1

    Returns: 0

  63. 132

    11

    Returns: -2

  64. 548

    15

    Returns: -2

  65. 474716

    79

    Returns: -290

  66. 375100

    93

    Returns: -92

  67. 474617

    89

    Returns: -1576

  68. 395367

    91

    Returns: -488

  69. 395368

    91

    Returns: -488

  70. 463079

    95

    Returns: -1260

  71. 463080

    95

    Returns: -1260

  72. 396882

    98

    Returns: -2

  73. 412717

    103

    Returns: -748

  74. 370424

    106

    Returns: -2

  75. 370483

    109

    Returns: -2

  76. 372241

    110

    Returns: -32

  77. 474747

    1000

    Returns: 959

  78. 474747

    10000

    Returns: 95

  79. 474747

    999

    Returns: 959

  80. 400000

    20000

    Returns: 41

  81. 434213

    414518

    Returns: 3

  82. 444444

    444444

    Returns: 1

  83. 471647

    3000

    Returns: 315

  84. 474747

    100

    Returns: -1902

  85. 470000

    20000

    Returns: 47

  86. 474746

    474746

    Returns: 1

  87. 474747

    100000

    Returns: 9

  88. 474747

    500

    Returns: 1935

  89. 474747

    99999

    Returns: 9

  90. 474000

    101

    Returns: -1872

  91. 474747

    5000

    Returns: 191

  92. 470000

    150000

    Returns: 7

  93. 474747

    4747

    Returns: 201

  94. 474747

    15000

    Returns: 63

  95. 474747

    474000

    Returns: 3

  96. 474373

    20

    Returns: -8

  97. 474700

    29

    Returns: -4

  98. 474747

    110

    Returns: -1746

  99. 222222

    4242

    Returns: 105

  100. 474743

    200000

    Returns: 5

  101. 80606

    43

    Returns: -34

  102. 4

    1

    Returns: 1

  103. 474747

    9

    Returns: 0

  104. 6

    1

    Returns: 3

  105. 49

    3

    Returns: -6

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: