POJ 2975 - Nim

http://poj.org/problem?id=2975

概要

Nim というゲームは二人で行い，n 個の石の山から交互に，1つの山から好きな数だけ石を取り除いていき，最終的にすべて取り除いたプレイヤーの勝ちである．

このゲームには，両プレイヤーが perfect にプレイしたときに先手が負ける losing という状態があり，これは各山の石の数を k[1], ..., k[n] とすると，k[i] の xor が 0 のときであることが知られている．

現在の状態から losing 状態にする一手を winning move という．

n 個の山のそれぞれの石の数が与えられるので，その状態からの winning move が何種類存在するかを答える．

制約

解法

k[i] の xor の値を X とすると，i 番目の山から石を取り除いて losing 状態にするには，k[i] を X xor k[i] に変えればいい． この操作を行えるのは X xor k[i] が k[i] より小さいときのみ．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     vector<long long> ks(N);
10     long long x = 0LL;
11     for (int i = 0; i < N; i++) {
12       scanf("%lld", &ks[i]);
13       x ^= ks[i];
14     }
15 
16     int c = 0;
17     for (int i = 0; i < N; i++) {
18       if ((x ^ ks[i]) < ks[i]) {
19         ++c;
20       }
21     }
22     printf("%d\n", c);
23   }
24   return 0;
25 }
poj/2975.cc