SPOJ.com - Problem NINJA8

NINJA8 - George vs Kramer

no tags

George and Kramer are in a serious fight. Seeing this, Jerry comes to convince them and settle the fight with a reasonable task. Knowing about their fondness of stamps, he creates a wonderful task for them. They are given N containers each having one or more stamps. Containers are numbered from 1 to N, where ith container has A[i] number of stamps. The game goes as follows. The first player will choose a container and take one or more stamps from it. Then, the second player will choose a non-empty container and take one or more stamps from it. And then they repeat this alternatively. This process will continue, until one of the players is not able to take any stamps, i.e., there are no stamps left. One who is not able to take any stamps loses the game. Note that player can choose only non-empty container.

Luckily George somehow got the first chance. He wants to know the number of ways to make a first move such that under optimal play, he wins. Being so poor at math and programming, he asks for your help. Help him!

Input Format:

The first line has an integer T, the number of test cases.

Then for each test case, the first line contains an integer N, i.e., number of containers and the second line contains N integers, i.e., number of stamps in each of the containers separated by a single space.

Output Format

Print the number of ways to make the first move such that under optimal play, George always wins. If he cannot win under optimal play, print 0.

Constraints

1 ≤ T ≤ 50

1 ≤ N ≤ 10⁶

1 ≤ A[i] ≤ 10⁹

Sample

Input:
1
2
2 3

Output:
1

Submit solution!

hide comments



	Rafail Loizou: 2021-02-28 06:07:53 grundy nymbers -> O(n) solution. Read the articles: https://en.wikipedia.org/wiki/Nimber https://www.geeksforgeeks.org/combinatorial-game-theory-set-3-grundy-numbersnimbers-and-mex/ then solve. This question requires knowledge rather than skill. I did not spoil the answer rather I spoil the knowledge.
	utkarsh5: 2016-03-15 14:38:04 @aqua_regia There are 5 possibilities for the case above. 1 or 2 from A[1], and 1 or 2 or 3 from A[2]. If he takes 2 from A[1] or 3 from A[2] he would clearly lose as his opponent will just take the remaining stamps from the other container. This leaves us with 3 cases. If he chooses 1 from A[1], the opponent (under optimal play) will pick 2 from A[2], which means that George will have to pick 1 from either of the two containers and then Kramer would win. Similarly, if he takes 2 from A[2], Kramer would take 1 from A[1] and George would lose again. Only when George takes 1 from A[2], there is no possible move for Kramer where George won't win. Therefore the answer is 1. I have assumed 1-indexed array and optimal play from both sides. Also, a move means choosing some number of stamps from any non-empty box. Hope this helps. :) Last edit: 2016-03-15 14:40:11
	aqua_regia: 2016-03-14 10:20:46 What does move means here? Choosing a box or choosing the box and the number of stamps in it? And how is the answer of test case 1,it should be 2, under optimal play he can choose any of the containers on his first move and he will win. Please explain .