POJ-2315 : Football Game
問題概要
問題文がかなり不親切なので適当に補完してまとめるとこんな感じ。
N個の山があるNimがある。同時に1~M個まで山を選んで石を1~K個まで自由に取り除くことができる。最後に取った方が勝ち(=有効手が選べない方の負け)。どちらが勝つか判定する問題。
解法
最大K個までとれる、というのは各山の個数を%(K+1)したものを考えればよい。なぜならK個以上あった場合、相手の番でa個とられても自分の番でK+1-a個取ってキャンセルできるから。
後は普通のM個平行のNimなので2進数表記して各桁%(M+1)とるだけでよい。
acceptされたコード
#include <cstdio> #include <cmath> #include <cstring> using namespace std; const int MAX_N = 30; const double PI = atan(1.0) * 4.0; int N, M, L, R; int xs[MAX_N], xors[50]; bool init() { if (scanf("%d%d%d%d", &N, &M, &L, &R) == EOF) { return false; } for (int i = 0; i < N; ++i) { scanf("%d", xs + i); } return true; } bool solve() { memset(xors, 0, sizeof(xors)); const int mod = (int)(L / (2 * R * PI)) + 1; for (int i = 0; i < N; ++i) { int g = (int)(1.0 + xs[i] / (2 * R * PI)) % mod; for (int j = 0; g; ++j, g >>= 1) { xors[j] += g & 1; } } for (int i = 0; i < 50; ++i) { if (xors[i] % (M + 1)) { return true; } } return false; } int main() { for (;init();) { puts(solve() ? "Alice" : "Bob"); } return 0; }