Statistics

Problem Statement for "MagicNim"

Problem Statement

Alice and Bob are playing a game of Nim with n+1 piles of stones. The piles are numbered from 0 to n. For each i between 0 and n-1, inclusive, pile i contains exactly a[i] normal stones. Pile n contains exactly one magic stone.

Normal rules of Nim apply to this game: Alice and Bob take alternating turns, with Alice going first. In each turn the current player chooses a non-empty pile (between 0 and n, inclusive) and removes an arbitrary positive number of stones from the pile. The player who is unable to make a valid move loses the game. In other words, the winner is the player who removes the very last stone.

Additionally, there is a rule for the magic stone. When a player chooses pile n and removes the magic stone, they have the option to reverse the victory condition. If they choose to do so, the player who is unable to make a valid move now wins the game. If they choose not to do it, the game continues with the original victory condition.

You are given the int[] a with n elements. (Note that the pile with the magic stone is not explicitly mentioned in a.)

Help Alice and Bob determine the winner of the game, assuming both of them play optimally. Return the name of the winner: either "Alice" or "Bob".

Definition

Class:
MagicNim
Method:
findWinner
Parameters:
int[]
Returns:
String
Method signature:
String findWinner(int[] a)
(be sure your method is public)

Constraints

  • a will contain between 1 and 10 elements, inclusive.
  • Each element of a will be between 1 and 50, inclusive.

Examples

  1. {1}

    Returns: "Alice"

    There are two piles. The first pile is a normal pile with one stone. The second pile contains the magic stone. In this case, Alice can take the magic stone and change the rules so that the last person who takes a stone loses. Now, Bob is forced to take the stone in the first pile, and since that is the last available stone, he loses.

  2. {2}

    Returns: "Bob"

    There are two piles. The first pile is a normal pile with two stones. The second pile contains the magic stone. In this case, no matter what Alice does, she will lose.

  3. {1,1,1,1}

    Returns: "Alice"

  4. {1,1,1,1,1}

    Returns: "Alice"

  5. {1,3}

    Returns: "Bob"

  6. {4,4,2}

    Returns: "Alice"

  7. {50,50,50,50,50,50,50,50,50,50}

    Returns: "Alice"

  8. {6,7}

    Returns: "Bob"

  9. {30}

    Returns: "Alice"

  10. {20,50,29,17,35,45,24,35}

    Returns: "Alice"

  11. {34,44}

    Returns: "Alice"

  12. {28,39,43,27,17,7,44,49,22}

    Returns: "Alice"

  13. {34,2,46,8}

    Returns: "Alice"

  14. {32,5,8}

    Returns: "Alice"

  15. {10,48,29,18,12,29,16}

    Returns: "Alice"

  16. {13,27}

    Returns: "Alice"

  17. {25,38,19,38}

    Returns: "Alice"

  18. {1,5,50}

    Returns: "Alice"

  19. {48,12,44}

    Returns: "Alice"

  20. {8,16,42,23,5,17,32,21}

    Returns: "Alice"

  21. {34,37}

    Returns: "Alice"

  22. {24,2,40,29,18}

    Returns: "Alice"

  23. {40,19,37,27}

    Returns: "Alice"

  24. {6,41,13,50,11,22,37,47,45,11}

    Returns: "Alice"

  25. {32,4,20,30,18}

    Returns: "Alice"

  26. {43,6,15,32,1,28}

    Returns: "Alice"

  27. {6,20,38,19,50,23,35,24}

    Returns: "Alice"

  28. {14,33,41,6,5,49,38,7}

    Returns: "Alice"

  29. {5,3,18,13}

    Returns: "Alice"

  30. {29,13,13,13,48,13,31}

    Returns: "Alice"

  31. {15,41,15}

    Returns: "Alice"

  32. {33,42,46,28,2}

    Returns: "Alice"

  33. {44,28,44,36,1,28,30,15}

    Returns: "Alice"

  34. {36,10,9,16,9}

    Returns: "Alice"

  35. {49,41,43,30,12,1,12}

    Returns: "Alice"

  36. {40,14,22,8,23,16,19,47}

    Returns: "Alice"

  37. {12,10,21,35,15,23,37}

    Returns: "Alice"

  38. {3,43,34,48,9,11,25,17,2}

    Returns: "Alice"

  39. {14,45,2,23,22,37,22,28}

    Returns: "Alice"

  40. {1,3,3}

    Returns: "Alice"

  41. {1,3,1,3,1,2,2}

    Returns: "Alice"

  42. {3,1,3,1}

    Returns: "Alice"

  43. {2,2,3,2,3,2,2}

    Returns: "Bob"

  44. {2,2,1,1,3,3,1,2,2}

    Returns: "Alice"

  45. {2,3,2,3,2,3}

    Returns: "Alice"

  46. {3,2,3,1,2,1,3,1,1,3}

    Returns: "Alice"

  47. {2,1,1,2,1}

    Returns: "Alice"

  48. {3,2,3,3}

    Returns: "Alice"

  49. {3,2,1,1,3,2,2,1,1,3}

    Returns: "Alice"

  50. {3,3,3,1}

    Returns: "Bob"

  51. {2,2,2,1}

    Returns: "Alice"

  52. {1,2,1,2,1}

    Returns: "Alice"

  53. {1,1,2,1,1,3,3,3,3}

    Returns: "Bob"

  54. {2,1,3,2,2,1,1,1}

    Returns: "Alice"

  55. {2,2,2,3,2,3,3}

    Returns: "Alice"

  56. {1,1,3,1}

    Returns: "Bob"

  57. {1,2,1,1,2,2,3,2,1}

    Returns: "Alice"

  58. {1,2,3,3,2,1,3,2}

    Returns: "Alice"

  59. {1,2,3,2,2,2,1,3}

    Returns: "Alice"

  60. {2,2}

    Returns: "Alice"

  61. {2,2,3,1,1,1,2,1,2,2}

    Returns: "Alice"

  62. {2,2,3,2,3,1}

    Returns: "Alice"

  63. {3,3,2}

    Returns: "Bob"

  64. {3,3,2,2,2,3}

    Returns: "Alice"

  65. {2,2,3,1,3,1,2,1,3,1}

    Returns: "Alice"

  66. {3,2,2,3,3,3,3,3,1}

    Returns: "Alice"

  67. {1,3,2,1,2,3,1,2}

    Returns: "Alice"

  68. {1,1,3,2,3,1,2,3}

    Returns: "Bob"

  69. {3,1,3,3,3,1,1,1}

    Returns: "Alice"

  70. {2,5,3,2,2,4,4,3,1}

    Returns: "Alice"

  71. {1,3,5,1,2}

    Returns: "Alice"

  72. {1,4}

    Returns: "Alice"

  73. {3,2,3,1,3,2}

    Returns: "Bob"

  74. {1,1,3}

    Returns: "Alice"

  75. {1,4,3,4,5}

    Returns: "Alice"

  76. {5,3,1,2,1,2,5,2,1,2}

    Returns: "Alice"

  77. {2,3,2,1,3,1,1}

    Returns: "Alice"

  78. {1,2,1,4,1,3,4}

    Returns: "Alice"

  79. {3,2,1}

    Returns: "Alice"

  80. {1,3,3,1,2,2,2,1,2}

    Returns: "Alice"

  81. {2,4,5}

    Returns: "Alice"

  82. {1,1,2,1}

    Returns: "Alice"

  83. {3,2,3,4,5,1,4}

    Returns: "Alice"

  84. {5,1,5,1,5}

    Returns: "Alice"

  85. {2,3,2,1,3,3}

    Returns: "Bob"

  86. {4,5,5}

    Returns: "Alice"

  87. {1,1,4}

    Returns: "Alice"

  88. {4,3,5,4,5,1}

    Returns: "Alice"

  89. {1,2,2,2,1,2,1,2,2}

    Returns: "Alice"

  90. {1,4,2,2,1,3,4,4}

    Returns: "Alice"

  91. {5,5,3,5,2,4}

    Returns: "Alice"

  92. {3,1,3,2,2,2,1,3,3,1}

    Returns: "Alice"

  93. {5,2,4,4,2,3,1,4}

    Returns: "Alice"

  94. {5,3,4,4,4,5,4}

    Returns: "Alice"

  95. {3,3,1,3,1,3,1,4,2,1}

    Returns: "Alice"

  96. {1,3,3,3,3,1,3,3,2}

    Returns: "Bob"

  97. {4,1,4,1,3,1,4}

    Returns: "Alice"

  98. {1,1,3,3,4,4,4}

    Returns: "Alice"

  99. {4,3,2,3,2,1,1,1}

    Returns: "Alice"

  100. {31,46,49,9,8}

    Returns: "Bob"

  101. {12,31,2,22,2,8,5,9}

    Returns: "Bob"

  102. {41,21,12,49}

    Returns: "Bob"

  103. {35,34,1,12,46,16,15,33,49,44}

    Returns: "Bob"

  104. {39,18,50}

    Returns: "Alice"

  105. {48,49}

    Returns: "Bob"

  106. {29,46,50}

    Returns: "Bob"

  107. {25,13,3,16,8,16,42,36,16}

    Returns: "Bob"

  108. {45,23,8,50,1}

    Returns: "Bob"

  109. {37,46,8,18,4,45,4}

    Returns: "Alice"

  110. {41,35,3,8}

    Returns: "Bob"

  111. {25,8,16}

    Returns: "Bob"

  112. {47,38,35,25,16,39,44,41}

    Returns: "Bob"

  113. {27,13,30,39,41,7}

    Returns: "Bob"

  114. {41,22,13,48,46,45}

    Returns: "Bob"

  115. {35,21,3,16,26,37,27}

    Returns: "Bob"

  116. {8,35,14,7,43,13,29,29,26,31}

    Returns: "Bob"

  117. {43,17,32,2,38,39,24}

    Returns: "Bob"

  118. {20,11,50,7,46,13,8}

    Returns: "Bob"

  119. {27,12,30,24,22,26,3,7,24}

    Returns: "Bob"

  120. {2,2,1}

    Returns: "Alice"

  121. {2,2,2}

    Returns: "Bob"

  122. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: "Alice"

  123. {3 }

    Returns: "Alice"

  124. {4, 4, 2 }

    Returns: "Alice"

  125. {3, 1, 2, 2 }

    Returns: "Bob"

  126. {2, 2, 2 }

    Returns: "Bob"

  127. {2, 3 }

    Returns: "Alice"

  128. {10, 11 }

    Returns: "Bob"

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: