Nim is the most famous two-player algorithm game. The basic rules for this game are as follows:
The game starts with a number of piles of stones. The number of stones in each pile may not be equal.
The players alternately pick up or more stones from pile
The player to remove the last stone wins.
For example, there are piles of stones having stones in them. Play may proceed as follows:
Player Takes Leaving
1 2 from pile pile=[3,4]
2 2 from pile pile=[3,2]
1 1 from pile pile=[2,2]
2 1 from pile pile=[1,2]
1 1 from pile pile=[1,1]
2 1 from pile pile=[0,1]
1 1 from pile WIN
Given the value of and the number of stones in each pile, determine the game's winner if both players play optimally.
Complete the nimGame function in the editor below. It should return a string, either First or Second.
nimGame has the following parameter(s):
pile: an integer array that represents the number of stones in each pile
The first line contains an integer, , denoting the number of games they play.
Each of the next pairs of lines is as follows:
The first line contains an integer , the number of piles.
The next line contains space-separated integers , the number of stones in each pile.
Player 1 always goes first.
For each game, print the name of the winner on a new line (i.e., either First or Second).
2 1 4
In the first case, there are piles of stones. Player has to remove one pile on the first move. Player removes the second for a win.
In the second case, there are piles of stones. If player removes any one pile, player can remove all but one of another pile and force a win. If player removes less than a pile, in any case, player can force a win as well, given optimal play.