northcott游戏(博弈sg).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 29 行

//计算出sg值， g(v) = mex {g(w) | (v, w) ∈ E}.
//必败态sg值为 0
//因为有n行将进行n次博弈，g(v) = g(v1) ⊕ g(v2). 
#include <cstdio>
#include <string>
#define ABS(x) ((x)<0?-(x):(x))
int n,m;
int sg[1100];

int main()
{
	while (scanf("%d %d",&n,&m)==2) {
		for (int i=0;i<n;i++) {
			int t,j;
			scanf("%d %d",&t,&j);
			sg[i] = ABS(t-j)-1;
		}
		int xor = sg[0];
		for (i=1;i<n;i++) {
			xor ^= sg[i];
		}
		if (xor == 0) {
			printf("BAD LUCK!\n");
		}
		else {
			printf("I WIN!\n");
		}
	}
}