POJ 1740 A New Stone Game

Problem Description:
There are N piles of stones, each with no more than 100 stones.
Two players play this game, when it is one's turn, one should:
Select a non-empty pile, remove at least one stone, then take arbitrary number of stones from the remaining stones in the pile, and arrange them to be added to arbitrary number of the other piles. The first player who couldn't make a move loses the game. Output whether the first player would win the game.

Constraints:
1 ≤ N ≤ 10

Solution:
Let us pair piles with identical number of stones together. If the piles in some state can be perfectly paired, this is a losing state, because whatever the first player does, the second player needs only to mimic his move, which in the end leads to the first player's losing state. However, if there is at least one pile that cannot be paired, we can always modify all the piles so that they are perfectly paired. We need only to consider the set of piles that are not paired. Suppose that they are sorted by their size. We can observe that the largest pile must be larger than the sum of each adjacent pile's difference of size. Suppose this set contains odd number of piles, then we only need to distribute stones from the largest pile to each odd indexed piles (1 based), and remove itself. Otherwise, move the largest pile to the front and distribute stones from it to each odd indexed piles, and remove the stones if there is more than the second pile.

Code:

#include <iostream>
#include <vector>

signed main() {
  std::ios::sync_with_stdio(false);
  int n;
  while (std::cin >> n && n) {
    std::vector<int> vec(100 + 1);
    for (int i = 0; i < n; ++i) {
      int x;
      std::cin >> x;
      ++vec[x];
    }
    bool any_odd = false;
    for (int i = 1; i < 101; ++i) {
      any_odd |= vec[i] & 1;
    }
    std::cout << any_odd << std::endl;
  }
  return 0;
}