Problem Description
Mr. Panda and Rar the Cat have been playing the very common game of Nim. The game of Nim works as follows. The game starts with N piles of stones and in the two players play alternately. In every move, a player will select a pile of stones and take any number of stones they want from that pile. The player who takes the last stone wins.
After playing many games, the intelligent Mr. Panda and Rar the Cat have figured out what the winning conditions are and the winning strategies for each player so the game becomes very boring. Hence, they decide to vary the game. They add an additional rule that after every move, there must be at least 2 piles with the same number of stones, possibly 0. The first player who does not have a valid move will lose. After playing and investigating many rounds, they hypothesised that if the first player had a "pass" that he can use within the first floor(sqrt(N)) moves, the first player will always win. They decide to have you play the game with them to prove this hypothesis.
Implementation
Your will be playing as the first player and will be playing with a computer program in alternate moves. Your code must implement the following 2 functions
void init(int N, int A[]): Initialisation function with the initial state given. N is the number of piles and A[0],A[1]...A[N-1] represent the number of stones in piles 1,2,...,N respectively. It is guaranteed that in the initial state, there will be 2 piles that have the same number of stones.
pair <int,int> move(int N, int A[])It is your turn and the state is provided as described above. Make a move by returning a pair<int,int> whose first number is the pile you want to remove from, in the range 1,2,...,N, the second number is the number of stones. If you want to pass, return (0,0) and no stones will be removed
It is guaranteed that your opponent will always make a valid move and takes negligible time to make the move. If you make an invalid move such as returning a pile number out of range, taking more stones than there are in the pile, passing after making floor(sqrt(N)) moves or passing more than once, you automatically lose. The game will automatically end when one of the players makes the last valid move. You will only get marks for a subtask if you win all the games and it is guaranteed that you can always win if you play optimally. You may use the template samenim.cpp provided if you wish. If not, please remember to include the library "samenim.h" in your code.
Subtasks
Subtask 1(7%): 2 ≤ N ≤ 5, the total number of stones will not exceed 10
Subtask 2(19%): 2 ≤ N ≤ 10, the total number of stones will not exceed 20
Subtask 3(31%): 2 ≤ N ≤ 100, the total number of stones will not exceed 200
Subtask 4(43%): 2 ≤ N ≤ 1000, the total number of stones will not exceed 10000
Subtask 5(0%): Sample Test Case
Sample Test Case
The sample test case involves 3 piles of stones with 1,2,1 stones in each pile respectively. A possible game could go like this.
Player 1: pass
Player 2: [1,1,1]
Player 1: [1,1,0]
Player 2: [0,1,0]
Player 1: [0,0,0]
In this case, player 1 wins the game.