Statistics

Problem Statement for "MatchNim"

Problem Statement

Yvonne and Zara are playing a variant of a NIM game. The game they play is played with matchsticks.

At any moment, there are some piles of matches. The players take alternating turns. Each turn looks as follows:

  1. The current player chooses a nonempty pile of matches and takes some of them (at least one, possibly all) into her hand.
  2. Then, she may use some of the matches she's holding to set fire to some piles of matches. Each match can only be used to set fire to one of the piles. She gets to choose how many matches she'll use for this and which piles she'll burn. If the pile from which she picked up the matches is still not empty, she may choose it as one of the piles to burn. Piles that get burned are considered empty for the purpose of the game.
  3. Finally, she discards the remaining matches she still holds, if any.

Yvonne goes first. The player who cannot make a valid move loses.

You are given the initial numbers of matches in the piles in the int[] piles. Return a String with the name of the girl who wins the game, assuming both of them play optimally.

Definition

Class:
MatchNim
Method:
whoWins
Parameters:
int[]
Returns:
String
Method signature:
String whoWins(int[] piles)
(be sure your method is public)

Constraints

  • piles will contain between 1 and 9 elements, inclusive.
  • Each element of piles will be between 1 and 1,000, inclusive.

Examples

  1. {1, 1, 1}

    Returns: "Zara"

    Regardless of what Yvonne does in her first move, Zara will be able to clear away the remaining matches and then Yvonne won't have any valid moves left and she will lose the game.

  2. {2, 2, 2, 2}

    Returns: "Yvonne"

    Yvonne wins by picking up a single match from any one of the piles.

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

    Returns: "Zara"

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

    Returns: "Yvonne"

    One of the winning moves for Yvonne in this situation is to pick up two matches from the largest pile, use one of them to burn one of the piles of size 3, and discard the other one. After Yvonne makes this move, the remaining piles will be {1, 3, 3, 3, 2}.

  5. {23, 6, 1, 1, 4, 6}

    Returns: "Yvonne"

  6. {7, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: "Yvonne"

  7. {47}

    Returns: "Yvonne"

  8. {7, 7, 7, 5, 7, 6, 7, 6, 7}

    Returns: "Zara"

  9. {1, 4, 6, 6, 7, 7, 7, 7, 7}

    Returns: "Zara"

  10. {1, 1, 2, 3, 4, 4, 6, 6, 6}

    Returns: "Zara"

  11. {1, 4, 5, 5, 5, 5, 6, 6}

    Returns: "Zara"

  12. {1, 2, 5, 7, 7, 7, 7, 7, 7}

    Returns: "Zara"

  13. {3, 4, 4, 6, 6, 6, 6, 6}

    Returns: "Zara"

  14. {1, 1, 2, 2, 4, 5, 5, 5}

    Returns: "Zara"

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

    Returns: "Zara"

  16. {1, 2, 3, 6, 6, 6, 6, 6}

    Returns: "Zara"

  17. {1, 1, 1, 1, 2, 3, 3, 3}

    Returns: "Zara"

  18. {1, 4, 5, 5, 6, 6, 6, 6}

    Returns: "Zara"

  19. {3, 4, 4, 5, 5, 6, 7, 7, 7}

    Returns: "Zara"

  20. {1, 2, 3, 4, 5, 6, 7, 7, 7}

    Returns: "Zara"

  21. {1, 2, 5, 6, 6, 7, 7, 7, 7}

    Returns: "Zara"

  22. {3, 3, 3, 5, 5, 7, 7, 7, 7}

    Returns: "Zara"

  23. {1, 2, 2, 2}

    Returns: "Zara"

  24. {2, 2, 6, 6, 7, 7, 7, 7, 7}

    Returns: "Zara"

  25. {2, 2, 5, 5, 5, 5, 6, 6}

    Returns: "Zara"

  26. {3, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: "Zara"

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

    Returns: "Zara"

  28. {1, 1, 1, 3, 3, 3, 3, 3}

    Returns: "Zara"

  29. {1, 3, 3, 5, 5, 6, 6, 6}

    Returns: "Zara"

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

    Returns: "Zara"

  31. {2, 2, 2, 2, 2, 2}

    Returns: "Zara"

  32. {1, 2, 4, 4, 5, 5, 6, 6}

    Returns: "Zara"

  33. {2, 2, 3, 3, 5, 6, 6, 6}

    Returns: "Zara"

  34. {2, 4, 5, 5, 5, 6, 6, 7, 7}

    Returns: "Zara"

  35. {1, 1, 3, 3, 3, 3, 5, 5, 5}

    Returns: "Zara"

  36. {3, 3, 3, 4, 5, 6, 7, 7, 7}

    Returns: "Zara"

  37. {1, 4, 5, 5, 5, 5, 7, 7, 7}

    Returns: "Zara"

  38. {3, 3, 3, 4, 5, 5, 5}

    Returns: "Zara"

  39. {1, 3, 3, 4, 5, 7, 7, 7, 7}

    Returns: "Zara"

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

    Returns: "Zara"

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

    Returns: "Zara"

  42. {1, 1, 4, 4, 4, 4, 5, 5}

    Returns: "Zara"

  43. {2, 4, 5, 6, 7, 7, 7, 7, 7}

    Returns: "Zara"

  44. {1, 3, 3, 4, 4, 6, 7, 7, 7}

    Returns: "Zara"

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

    Returns: "Zara"

  46. {3, 3, 3, 4, 4, 4}

    Returns: "Zara"

  47. {1, 3, 3, 6, 6, 6, 6, 7, 7}

    Returns: "Zara"

  48. {1, 2, 3, 4, 7, 7, 7, 7, 7}

    Returns: "Zara"

  49. {1, 4, 4, 3, 3, 4}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  52. {5, 3, 4, 2, 1, 5, 3, 6}

    Returns: "Yvonne"

  53. {3, 5, 3, 5, 5, 7, 2, 2, 7}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  56. {5, 3, 3, 2, 5, 3, 3}

    Returns: "Yvonne"

  57. {5, 1, 4, 3, 5, 4, 3, 6}

    Returns: "Yvonne"

  58. {2, 5, 1, 6, 2, 4, 4, 3}

    Returns: "Yvonne"

  59. {5, 2, 4, 1, 2, 5, 6, 1}

    Returns: "Yvonne"

  60. {2, 2, 2, 2}

    Returns: "Yvonne"

  61. {2, 2, 2, 1}

    Returns: "Zara"

  62. {2, 2, 3, 4, 6, 2, 2, 4}

    Returns: "Yvonne"

  63. {1, 1, 1, 3, 3}

    Returns: "Yvonne"

  64. {4, 1, 3, 4, 1, 1}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  66. {5, 7, 4, 2, 7, 7, 7, 4, 5}

    Returns: "Yvonne"

  67. {5, 5, 1, 1, 2, 2, 5}

    Returns: "Yvonne"

  68. {1, 2, 1, 4, 1, 1}

    Returns: "Yvonne"

  69. {2, 1, 2, 1}

    Returns: "Yvonne"

  70. {6, 5, 2, 5, 5, 3, 5, 5}

    Returns: "Yvonne"

  71. {2, 2, 1, 1}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  73. {1, 2, 2, 1}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  75. {2, 2, 1, 2, 1}

    Returns: "Yvonne"

  76. {1, 6, 4, 4, 3, 6, 5, 6}

    Returns: "Yvonne"

  77. {6, 1, 5, 2, 7, 6, 3, 1, 7}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  79. {3, 4, 6, 2, 6, 6, 1, 1}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  81. {4, 3, 1, 3, 5, 7, 1, 4, 6}

    Returns: "Yvonne"

  82. {3, 2, 3, 2, 4, 3}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  84. {2, 2, 2, 2}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  87. {1, 5, 6, 4, 5, 5, 6, 5}

    Returns: "Zara"

  88. {5, 4, 5, 5, 2, 6, 6, 4, 7}

    Returns: "Yvonne"

  89. {2, 2, 1, 4}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  91. {3, 2, 7, 1, 7, 8, 8, 6}

    Returns: "Yvonne"

  92. {2, 9, 7, 2, 2, 7, 7, 9, 2}

    Returns: "Yvonne"

  93. {3, 8, 8, 8, 2, 7, 6, 7}

    Returns: "Yvonne"

  94. {4, 6, 7, 2, 3, 8, 6, 2, 5}

    Returns: "Yvonne"

  95. {7, 1, 3, 1, 4, 5, 1}

    Returns: "Yvonne"

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

    Returns: "Yvonne"

  97. {6, 2, 4, 5, 4, 1, 5}

    Returns: "Yvonne"

  98. {5, 2, 6, 5, 3, 7, 7}

    Returns: "Yvonne"

  99. {346, 66, 161, 605}

    Returns: "Yvonne"

  100. {245, 865, 887, 188}

    Returns: "Yvonne"

  101. {146, 528, 173, 737}

    Returns: "Yvonne"

  102. {80, 95, 129, 604, 404}

    Returns: "Yvonne"

  103. {125, 985, 425, 302, 563, 656}

    Returns: "Yvonne"

  104. {696, 940, 356, 788, 93}

    Returns: "Yvonne"

  105. {322, 105, 37, 207, 831, 573, 139, 987, 339}

    Returns: "Yvonne"

  106. {854, 327, 788, 733}

    Returns: "Yvonne"

  107. {962, 968, 939, 440, 519, 560, 587, 771, 789}

    Returns: "Yvonne"

  108. {923, 361, 817, 534, 532, 436, 654, 450, 447}

    Returns: "Yvonne"

  109. {7, 7, 7, 7, 7, 7, 7, 7, 7 }

    Returns: "Yvonne"

  110. {7, 7, 7, 7, 3, 7, 7, 7, 7 }

    Returns: "Zara"

  111. {23, 6, 1, 1, 4, 6 }

    Returns: "Yvonne"

  112. {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    Returns: "Yvonne"

  113. {7, 7, 7, 7, 7, 7, 6, 6, 5 }

    Returns: "Zara"

  114. {5, 1, 5, 3, 3, 5, 5, 1 }

    Returns: "Yvonne"

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: