Statistics

Problem Statement for "StonesGame"

Problem Statement

Romeo and his friend Strangelet are playing a game. There are N stones in a row, all of which are black except for the M-th one, which is white (all positions in this problem are 1-based). The players alternate turns, and Romeo plays first. On each turn, a player must choose exactly K consecutive stones, one of which must be white, and reverse their order. The winner is the first player who puts the white stone in the L-th position. Return "Romeo" if Romeo can win regardless of how Strangelet plays, and return "Strangelet" if Strangelet can win regardless of Romeo's strategy. Otherwise, return "Draw" since neither player can win if both players play optimally. All quotes are for clarity only.

Definition

Class:
StonesGame
Method:
winner
Parameters:
int, int, int, int
Returns:
String
Method signature:
String winner(int N, int M, int K, int L)
(be sure your method is public)

Constraints

  • N will be between 2 and 1,000,000, inclusive.
  • M, K and L will each be between 1 and N, inclusive.
  • M and L will be different.

Examples

  1. 2

    1

    2

    2

    Returns: "Romeo"

  2. 3

    1

    1

    2

    Returns: "Draw"

    There are three stones and the stone in position 1 is white. To win the game, a player must put the white stone in position 2. However, since K is 1, each player can only choose a single stone to reverse, so it is impossible to move the white stone from its original position. Therefore, neither player can win.

  3. 5

    1

    2

    2

    Returns: "Romeo"

    Romeo can win on his first move by reversing the order of the first two stones.

  4. 5

    5

    2

    3

    Returns: "Strangelet"

    Romeo's only possible move is to reverse the last two stones. This puts the white stone in position 4. Strangelet can then reverse the third and fourth stones, putting the white stone in position 3 and winning the game.

  5. 5

    5

    2

    2

    Returns: "Draw"

    This is similar to the previous example, but here, the white stone must be moved to position 2. As in the previous example, Romeo's first move will put the white stone in position 4. This time, Strangelet will then move it back to position 5 because otherwise, Romeo would move it to position 2 and win. This sequence of moves will repeat infinitely and neither player will win.

  6. 2

    1

    1

    2

    Returns: "Draw"

  7. 2

    2

    1

    1

    Returns: "Draw"

  8. 2

    1

    2

    2

    Returns: "Romeo"

  9. 2

    2

    2

    1

    Returns: "Romeo"

  10. 3

    1

    1

    2

    Returns: "Draw"

  11. 3

    1

    1

    3

    Returns: "Draw"

  12. 3

    2

    1

    1

    Returns: "Draw"

  13. 3

    2

    1

    3

    Returns: "Draw"

  14. 3

    3

    1

    1

    Returns: "Draw"

  15. 3

    3

    1

    2

    Returns: "Draw"

  16. 3

    1

    2

    2

    Returns: "Romeo"

  17. 3

    1

    2

    3

    Returns: "Strangelet"

  18. 3

    2

    2

    1

    Returns: "Romeo"

  19. 3

    2

    2

    3

    Returns: "Romeo"

  20. 3

    3

    2

    1

    Returns: "Strangelet"

  21. 3

    3

    2

    2

    Returns: "Romeo"

  22. 3

    1

    3

    2

    Returns: "Draw"

  23. 3

    1

    3

    3

    Returns: "Romeo"

  24. 3

    2

    3

    1

    Returns: "Draw"

  25. 3

    2

    3

    3

    Returns: "Draw"

  26. 3

    3

    3

    1

    Returns: "Romeo"

  27. 3

    3

    3

    2

    Returns: "Draw"

  28. 10

    1

    8

    5

    Returns: "Strangelet"

  29. 9

    3

    3

    9

    Returns: "Draw"

  30. 6

    6

    4

    2

    Returns: "Strangelet"

  31. 6

    1

    3

    4

    Returns: "Draw"

  32. 8

    2

    5

    7

    Returns: "Draw"

  33. 9

    6

    8

    7

    Returns: "Draw"

  34. 7

    6

    2

    2

    Returns: "Draw"

  35. 10

    3

    9

    10

    Returns: "Draw"

  36. 10

    5

    10

    6

    Returns: "Romeo"

  37. 10

    4

    2

    3

    Returns: "Romeo"

  38. 8

    8

    1

    6

    Returns: "Draw"

  39. 10

    5

    9

    8

    Returns: "Draw"

  40. 9

    8

    7

    4

    Returns: "Romeo"

  41. 10

    9

    2

    10

    Returns: "Romeo"

  42. 9

    7

    3

    6

    Returns: "Draw"

  43. 5

    3

    2

    1

    Returns: "Draw"

  44. 9

    1

    5

    6

    Returns: "Draw"

  45. 7

    7

    3

    4

    Returns: "Draw"

  46. 8

    3

    8

    5

    Returns: "Draw"

  47. 10

    10

    9

    5

    Returns: "Draw"

  48. 1000000

    131525

    705444

    275309

    Returns: "Strangelet"

  49. 1000000

    251567

    705444

    6097

    Returns: "Draw"

  50. 1000000

    804588

    705444

    292263

    Returns: "Romeo"

  51. 1000000

    791181

    347709

    721626

    Returns: "Draw"

  52. 1000000

    43795

    347709

    506697

    Returns: "Strangelet"

  53. 1000000

    595477

    347709

    275837

    Returns: "Romeo"

  54. 1000000

    157692

    569590

    680270

    Returns: "Strangelet"

  55. 1000000

    141323

    569590

    144412

    Returns: "Draw"

  56. 1000000

    127671

    569590

    464318

    Returns: "Romeo"

  57. 1000000

    418768

    623197

    388979

    Returns: "Draw"

  58. 1000000

    205057

    623197

    459153

    Returns: "Romeo"

  59. 1000000

    187669

    623197

    410751

    Returns: "Strangelet"

  60. 1000000

    279207

    267101

    658544

    Returns: "Draw"

  61. 1000000

    897139

    267101

    646247

    Returns: "Romeo"

  62. 1000000

    986533

    267101

    708351

    Returns: "Strangelet"

  63. 1000000

    357987

    475408

    202189

    Returns: "Draw"

  64. 1000000

    971540

    475408

    333102

    Returns: "Strangelet"

  65. 1000000

    805503

    475408

    624982

    Returns: "Romeo"

  66. 1000000

    918661

    676615

    730548

    Returns: "Draw"

  67. 1000000

    238455

    676615

    664919

    Returns: "Romeo"

  68. 1000000

    821658

    676615

    801838

    Returns: "Strangelet"

  69. 1000000

    467470

    270595

    380885

    Returns: "Draw"

  70. 1000000

    662889

    270595

    600781

    Returns: "Romeo"

  71. 1000000

    922371

    270595

    910759

    Returns: "Strangelet"

  72. 1000000

    220322

    93517

    660116

    Returns: "Draw"

  73. 1000000

    374352

    93517

    354850

    Returns: "Romeo"

  74. 1000000

    965405

    93517

    861365

    Returns: "Strangelet"

  75. 1000000

    907614

    548991

    220911

    Returns: "Draw"

  76. 1000000

    238793

    548991

    242437

    Returns: "Strangelet"

  77. 1000000

    730836

    548991

    640234

    Returns: "Romeo"

  78. 999999

    1

    500000

    999999

    Returns: "Strangelet"

  79. 1000000

    100000

    500000

    600000

    Returns: "Strangelet"

  80. 1000000

    1000000

    1000000

    999999

    Returns: "Draw"

  81. 137

    85

    32

    116

    Returns: "Romeo"

  82. 954

    545

    2

    58

    Returns: "Draw"

  83. 6

    5

    1

    2

    Returns: "Draw"

  84. 7

    1

    7

    5

    Returns: "Draw"

  85. 42

    1

    2

    17

    Returns: "Draw"

  86. 232

    1

    160

    2

    Returns: "Draw"

  87. 96

    85

    21

    65

    Returns: "Romeo"

  88. 4

    1

    4

    3

    Returns: "Draw"

  89. 3

    1

    3

    3

    Returns: "Romeo"

  90. 946

    243

    1

    426

    Returns: "Draw"

  91. 44

    13

    2

    30

    Returns: "Draw"

  92. 36

    36

    26

    14

    Returns: "Draw"

  93. 153

    153

    63

    44

    Returns: "Draw"

  94. 6

    2

    4

    6

    Returns: "Draw"

  95. 5

    1

    4

    2

    Returns: "Draw"

  96. 6

    4

    3

    1

    Returns: "Draw"

  97. 1000000

    494613

    498765

    999813

    Returns: "Draw"

  98. 1000000

    999998

    3899

    5

    Returns: "Draw"

  99. 5

    1

    3

    2

    Returns: "Draw"

  100. 1000

    333

    412

    612

    Returns: "Romeo"

  101. 10

    1

    10

    5

    Returns: "Draw"

  102. 1000000

    123

    12

    1231

    Returns: "Draw"

  103. 999999

    834753

    483140

    999925

    Returns: "Draw"

  104. 1000

    45

    2

    67

    Returns: "Draw"

  105. 4

    1

    4

    2

    Returns: "Draw"

  106. 1000000

    76543

    7896

    789657

    Returns: "Draw"

  107. 5

    4

    4

    5

    Returns: "Draw"

  108. 5

    4

    5

    5

    Returns: "Draw"

  109. 5

    1

    5

    2

    Returns: "Draw"

  110. 999997

    7943

    1327

    999977

    Returns: "Draw"

  111. 1000000

    100000

    500000

    600002

    Returns: "Strangelet"

  112. 7

    4

    7

    6

    Returns: "Draw"

  113. 5

    4

    3

    5

    Returns: "Draw"

  114. 100

    50

    5

    51

    Returns: "Draw"

  115. 1000000

    2

    999999

    999997

    Returns: "Draw"

  116. 1000000

    499999

    2

    500001

    Returns: "Draw"

  117. 50000

    100

    100

    200

    Returns: "Draw"

  118. 7

    4

    4

    2

    Returns: "Draw"

  119. 100

    1

    3

    2

    Returns: "Draw"

  120. 1000000

    500000

    478

    877849

    Returns: "Draw"

  121. 5

    3

    3

    4

    Returns: "Draw"

  122. 10

    5

    5

    6

    Returns: "Draw"

  123. 4

    3

    3

    4

    Returns: "Draw"

  124. 100

    10

    5

    11

    Returns: "Draw"

  125. 6

    6

    5

    4

    Returns: "Strangelet"

  126. 1000000

    100000

    500001

    6000

    Returns: "Draw"

  127. 100

    99

    10

    100

    Returns: "Draw"

  128. 10

    3

    5

    6

    Returns: "Draw"

  129. 7

    3

    7

    4

    Returns: "Draw"

  130. 5

    3

    5

    4

    Returns: "Draw"

  131. 100

    30

    11

    25

    Returns: "Draw"

  132. 100000

    1

    9999

    8

    Returns: "Draw"

  133. 999337

    2

    999337

    1

    Returns: "Draw"

  134. 4

    2

    4

    4

    Returns: "Draw"

  135. 1000000

    100000

    200000

    500000

    Returns: "Draw"

  136. 6

    1

    6

    4

    Returns: "Draw"

  137. 1000000

    100000

    500000

    1

    Returns: "Draw"

  138. 6

    2

    6

    6

    Returns: "Draw"

  139. 10

    1

    10

    9

    Returns: "Draw"

  140. 9

    9

    4

    4

    Returns: "Draw"

  141. 7

    2

    5

    5

    Returns: "Draw"

  142. 10

    5

    4

    7

    Returns: "Draw"

  143. 100

    1

    99

    3

    Returns: "Strangelet"

  144. 10

    1

    6

    2

    Returns: "Draw"

  145. 5

    2

    2

    5

    Returns: "Draw"

  146. 4

    4

    4

    3

    Returns: "Draw"

  147. 10

    9

    3

    10

    Returns: "Draw"

  148. 10

    1

    4

    2

    Returns: "Draw"

  149. 10000

    400

    999

    512

    Returns: "Strangelet"

  150. 10

    2

    5

    8

    Returns: "Strangelet"

  151. 7

    4

    7

    5

    Returns: "Draw"

  152. 30

    10

    4

    16

    Returns: "Draw"

  153. 5

    1

    4

    3

    Returns: "Strangelet"

  154. 50

    25

    50

    30

    Returns: "Draw"

  155. 4

    2

    4

    1

    Returns: "Draw"

  156. 6

    6

    4

    4

    Returns: "Strangelet"

  157. 10

    5

    9

    9

    Returns: "Draw"

  158. 5

    2

    5

    3

    Returns: "Draw"

  159. 8

    1

    8

    3

    Returns: "Draw"

  160. 10

    4

    3

    5

    Returns: "Draw"

  161. 5

    4

    3

    3

    Returns: "Draw"

  162. 100

    1

    5

    2

    Returns: "Draw"

  163. 8

    5

    2

    3

    Returns: "Draw"

  164. 875973

    636549

    837344

    810904

    Returns: "Draw"

  165. 30

    1

    3

    2

    Returns: "Draw"

  166. 5

    5

    4

    4

    Returns: "Draw"

  167. 1000

    3

    97

    100

    Returns: "Draw"

  168. 1000000

    500000

    500001

    500001

    Returns: "Draw"

  169. 8

    1

    4

    2

    Returns: "Draw"

  170. 100

    99

    4

    100

    Returns: "Draw"

  171. 1000

    4

    3

    5

    Returns: "Draw"

  172. 6

    2

    5

    5

    Returns: "Draw"

  173. 8

    1

    8

    5

    Returns: "Draw"

  174. 5

    5

    5

    3

    Returns: "Draw"

  175. 5

    3

    5

    1

    Returns: "Draw"

  176. 8

    2

    4

    4

    Returns: "Strangelet"

  177. 100

    5

    4

    2

    Returns: "Romeo"

  178. 299999

    651

    154

    541

    Returns: "Draw"

  179. 5

    2

    2

    3

    Returns: "Romeo"

  180. 5

    2

    3

    3

    Returns: "Draw"

  181. 10

    5

    3

    6

    Returns: "Draw"

  182. 10

    2

    3

    8

    Returns: "Draw"

  183. 6

    3

    5

    1

    Returns: "Draw"

  184. 7

    2

    7

    4

    Returns: "Draw"

  185. 15

    5

    2

    3

    Returns: "Draw"

  186. 100

    10

    3

    12

    Returns: "Romeo"

  187. 11

    1

    9

    11

    Returns: "Draw"

  188. 100

    11

    5

    19

    Returns: "Draw"

  189. 1000000

    123321

    500000

    954845

    Returns: "Draw"

  190. 999999

    998742

    5482

    999934

    Returns: "Draw"

  191. 6

    6

    4

    5

    Returns: "Draw"

  192. 50000

    100

    100

    201

    Returns: "Draw"

  193. 5

    3

    5

    5

    Returns: "Draw"

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: