Statistics

Problem Statement for "TheNumberGameDivOne"

Problem Statement

John and Brus play a game with a number. The game starts with a positive integer n. The two players take alternating turns, John starts. Each move looks as follows: Let C be the current value of the integer. The current player has to choose a positive divisor of the number C, other than 1 and C. Once he chooses the divisor, he has to subtract it from C. The result is the new number with which the other player now starts his move. If a player cannot make a valid move, he loses the game.

For example, if they start with n=15, one possible gameplay can look as follows:
  • John takes the number 15, chooses its divisor 3, and decreases the number to 15-3 = 12.
  • Brus takes the number 12, chooses its divisor 4, and decreases the number to 12-4 = 8.
  • John takes the number 8, chooses its divisor 2, and decreases the number to 8-2 = 6.
  • Brus takes the number 6, chooses its divisor 3, and decreases the number to 6-3 = 3.
  • John takes the number 3, and as there are no divisors other than 1 and 3, he has no valid move and thus he loses the game.


You are given the long n. Assume that both players use the optimal strategy while playing the game. Return "John" (quotes for clarity) if John wins the game and "Brus" otherwise.

Definition

Class:
TheNumberGameDivOne
Method:
find
Parameters:
long
Returns:
String
Method signature:
String find(long n)
(be sure your method is public)

Constraints

  • n will be between 1 and 10^18, inclusive.

Examples

  1. 6

    Returns: "John"

    John has two possible moves: either decrease 6 by 2 or decrease 6 by 3. If he chooses the second option, Brus will have no possible moves, hence John will win the game.

  2. 2

    Returns: "Brus"

  3. 747

    Returns: "Brus"

  4. 128

    Returns: "Brus"

  5. 417

    Returns: "Brus"

  6. 223

    Returns: "Brus"

  7. 52

    Returns: "John"

  8. 483

    Returns: "Brus"

  9. 64

    Returns: "John"

  10. 488

    Returns: "John"

  11. 462

    Returns: "John"

  12. 778

    Returns: "John"

  13. 597

    Returns: "Brus"

  14. 556

    Returns: "John"

  15. 65

    Returns: "Brus"

  16. 231

    Returns: "Brus"

  17. 199

    Returns: "Brus"

  18. 992

    Returns: "John"

  19. 257

    Returns: "Brus"

  20. 830

    Returns: "John"

  21. 396

    Returns: "John"

  22. 469

    Returns: "Brus"

  23. 276

    Returns: "John"

  24. 802

    Returns: "John"

  25. 914

    Returns: "John"

  26. 543

    Returns: "Brus"

  27. 631

    Returns: "Brus"

  28. 45

    Returns: "Brus"

  29. 837

    Returns: "Brus"

  30. 860

    Returns: "John"

  31. 533

    Returns: "Brus"

  32. 373

    Returns: "Brus"

  33. 367

    Returns: "Brus"

  34. 259

    Returns: "Brus"

  35. 394

    Returns: "John"

  36. 16

    Returns: "John"

  37. 32

    Returns: "Brus"

  38. 256

    Returns: "John"

  39. 512

    Returns: "Brus"

  40. 64

    Returns: "John"

  41. 8

    Returns: "Brus"

  42. 5

    Returns: "Brus"

  43. 4

    Returns: "John"

  44. 3

    Returns: "Brus"

  45. 1

    Returns: "Brus"

  46. 999

    Returns: "Brus"

  47. 1000

    Returns: "John"

  48. 36028797018963968

    Returns: "Brus"

  49. 17179869184

    Returns: "John"

  50. 35184372088832

    Returns: "Brus"

  51. 17592186044416

    Returns: "John"

  52. 67108864

    Returns: "John"

  53. 4294967296

    Returns: "John"

  54. 2048

    Returns: "Brus"

  55. 4398046511104

    Returns: "John"

  56. 8388608

    Returns: "Brus"

  57. 140737488355328

    Returns: "Brus"

  58. 2097152

    Returns: "Brus"

  59. 137438953472

    Returns: "Brus"

  60. 72057594037927936

    Returns: "John"

  61. 777099619347749670

    Returns: "John"

  62. 657883257925660258

    Returns: "John"

  63. 58116120065062962

    Returns: "John"

  64. 539656914644202582

    Returns: "John"

  65. 485693912333408402

    Returns: "John"

  66. 37572215255261210

    Returns: "John"

  67. 875678191683108048

    Returns: "John"

  68. 494768164517789482

    Returns: "John"

  69. 106954493434730061

    Returns: "Brus"

  70. 315033728610403455

    Returns: "Brus"

  71. 1000000000000000000

    Returns: "John"

  72. 999999999999999999

    Returns: "Brus"

  73. 576460752303423488

    Returns: "Brus"

  74. 288230376151711744

    Returns: "John"

  75. 999999999999999989

    Returns: "Brus"

  76. 2199023255552

    Returns: "Brus"

  77. 12880097696556090

    Returns: "John"

  78. 1125899906842624

    Returns: "John"

  79. 999999866000004473

    Returns: "Brus"

  80. 999999874000003969

    Returns: "Brus"

  81. 944854643287051537

    Returns: "Brus"

  82. 20

    Returns: "John"

  83. 145248598745214582

    Returns: "John"

  84. 68719476736

    Returns: "John"

  85. 15

    Returns: "Brus"

  86. 25

    Returns: "Brus"

  87. 218409274160236512

    Returns: "John"

  88. 281474976710656

    Returns: "John"

  89. 144115188075855872

    Returns: "Brus"

  90. 100000000000000019

    Returns: "Brus"

  91. 100000000000000003

    Returns: "Brus"

  92. 100000000034598767

    Returns: "Brus"

  93. 12934872364872639

    Returns: "Brus"

  94. 9

    Returns: "Brus"

  95. 70368744177664

    Returns: "John"

  96. 999999999999999993

    Returns: "Brus"

  97. 40

    Returns: "John"

  98. 99999999999999999

    Returns: "Brus"

  99. 24

    Returns: "John"

  100. 18014398509481984

    Returns: "John"

  101. 14

    Returns: "John"

  102. 105

    Returns: "Brus"

  103. 10

    Returns: "John"

  104. 2197

    Returns: "Brus"

  105. 12

    Returns: "John"

  106. 999999999999999023

    Returns: "Brus"

  107. 744131759421141407

    Returns: "Brus"

  108. 1099511627776

    Returns: "John"

  109. 1024

    Returns: "John"

  110. 965211250482432409

    Returns: "Brus"

  111. 24272000000000002

    Returns: "John"

  112. 9007199254740992

    Returns: "Brus"

  113. 50

    Returns: "John"

  114. 10000001400000049

    Returns: "Brus"

  115. 2251799813685248

    Returns: "Brus"

  116. 34

    Returns: "John"

  117. 16888498602639360

    Returns: "John"

  118. 562949953421314

    Returns: "John"

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: