12 Game

All submissions for this problem are available.
There are two players $P_1$, $P_2$ playing a game on an array $A$ which has $n$ positive integers: $A_1, A_2, \ldots, A_n$. Both the players takes turns alternatively, and $P_1$ goes first. Rules of the game are as follows.  In $P_1$’s turn, he should choose any element $A_i$ which is $\ge 1$, and subtract $1$ from it.  In $P_2$’s turn, he should choose any element $A_i$ which is $\ge 2$, and subtract $2$ from it.  The player who is not able to make a move loses. Given the array $A$, find the number of different indices $i$ such that that $P_1$ can subtract from $A_i$ in his first turn, and end up winning the game, if both the players play optimally after this. ### Input  The first line of the input contains an integer $T$ denoting the number of test cases. The description of the test cases follows.  The first line of each test case contains an integer $n$.  The second line of each test case contains $n$ spaceseparated integers denoting the array $A$. ### Output For each test case, output an integer corresponding to the number of possible first moves of $P_1$ that lead him to win. ###Constraints  $1 \le T \le 10^5$  $1 \le n \leq 10^5$  $1 \le A_i \leq 10^5$  Sum of $n$ over all the test cases doesn't exceed $10^6$ ### Example Input ``` 3 1 1 1 3 2 1 2 ``` ### Example Output ``` 1 0 1 ``` ###Explanation **Testcase 1**: The array is {1}. $P_1$ has no choice but to pick the element and subtract 1 from it. The resulting array is {0}, and now $P_2$ is unable to make a move. Hence $P_1$ wins, and there was only one winning first move. Hence the answer is 1. **Testcase 2**: The array is {3}. $P_1$ has no choice but to pick the element and subtract 1 from it. The resulting array is {2}, and now $P_2$ has no choice but to subtract 2 from it. The resulting array is {0}, and now $P_1$ is unable to make a move. Hence $P_1$ loses.There is no starting move for $P_1$ which leads to his victory. Hence the answer is 0. **Testcase 3**: The array is {1, 2}. $P_1$ has two choices. Either subtract 1 from 1 or subtract 1 from 2.  Suppose he subtracts 1 from the first element, then the resulting array is {0, 2}, and now $P_2$ has no choice but to subtract 2 from the second element. The resulting array is {0, 0}, and now $P_1$ is unable to make a move. Hence $P_1$ loses in this case.  But suppose he subtracts 1 from the second element, then the resulting array is {1, 1}, and now $P_2$ is unable to make a move. Hence $P_1$ wins in this case. Thus, there is exactly one starting move for $P_1$ which leads to his victory. Hence the answer is 1.Author:  admin2 
Tags  admin2 
Date Added:  13122018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions