This is a classic Game Theory problem. We are told there are two players, Jack and Jim, in a game with N distinct pile(s) of stones, where each pile has Pi stones (i.e., i = 1..N, 1 <= Pi <= 2 * 109). Jack and Jim take turns removing some stones until all have been removed. At that point, the player who removed the last stone is declared the winner. On each turn, the active player chooses one of the remaining piles and removes a number of stones (greater than zero, but not more than the number of stones remaining in the selected pile) from the selected pile only. For each test case, represented by the initial game state, we want to know if Jack will win or lose, assuming both players perform optimally. Jack will always go first. Let's start by noticing an important property that holds true when there are two piles (i.e., N = 2, P1 = P2). Under these conditions, the player who takes his turn 2nd will always win. Consider the following sample input containing three test cases that demonstrate this condition:
2
1 1
2
2 2
2
3 3
0
In the first case (i.e., N = 2, P1 = P2 = 1), the game will play out as follows: (1) Jack takes 1 from one of two piles, (2) Jim takes 1 from the last pile, (3) Jim wins. In the second case (i.e., N = 2, P1 = P2 = 2), there are a few more (equally optimal) ways the game can play out, however, the result is the same as the first case. On the first turn, Jack may take one or two stones from one of the piles. If he takes one stone, Jim's optimal move is to take one stone from the opposite pile and thereby creating a game state that is effectively identical to the first case, in which Jim always wins. If, instead, Jack chooses to take two stones from one of the piles, Jim will take two stones from the opposite pile and win the game.
Similarly for the third case. Whenever Jack takes his turn and there are only two piles, each with an equal number of stones, Jim is certain to win. We can extend this idea to game states with more than two piles. If, at the beginning of a player's turn, there are M equal piles remaining, the active player is guaranteed to win when M is odd. If M is even, the passive player will win. This observation alone should help steer you towards a solution for this problem. Try drawing decision trees for small cases and see if you can't spot a pattern. This is the essence of competitive programming! Perhaps you will come to understand the underlying theory of what Charles L. Bouton coined as the "Nim" game. Our observations above are related to what Bouton referred to as safe combinations[1]. It turns out there is a very elegant solution to determining a winner.
For a game with N distinct piles, in which the number of stones in the ith pile is equal to Pi, for i = 1, 2, ..., N, Jack is guaranteed to win the game if the value of P1 ⊕ ... ⊕ PN is non-zero (⊕ is bitwise XOR). Otherwise, Jim (i.e., 2nd player) will win. That's it! I encourage you to check out Bouton's proof, it will really help cement this problem type into your mind and promise you easy points when you see it in competition.