Connection Status:
Competition Arena > MatchNim

MatchNim

SRM 757 · 2019-04-28 · by misof

SRM 757 · 2019-04-28 · by misof · Dynamic Programming, Math
Class Name: MatchNim
Return Type: String
Method Name: whoWins
Arg Types: (vector<int>)
Problem Statement

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.

Constraints

  • piles will contain between 1 and 9 elements, inclusive.
  • Each element of piles will be between 1 and 1,000, inclusive.
Examples
0)
{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.

1)
{2, 2, 2, 2}
Returns: "Yvonne"

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

2)
{3, 1, 3, 2, 3}
Returns: "Zara"
3)
{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}.

4)
{23, 6, 1, 1, 4, 6}
Returns: "Yvonne"

Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MatchNim with a public method string whoWins(vector<int> piles) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous