Cod sursa(job #279541)

Utilizator tvladTataranu Vlad tvlad Data 12 martie 2009 21:03:38
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <vector>
using namespace std;

const int SG_MAX = 100;

int SG[SG_MAX];

void build_sg() {
	SG[0] = 0; SG[1] = 1; SG[2] = 2;
	vector<bool> view(SG_MAX);
	for (int i = 3; i < SG_MAX; ++i) {
		fill(view.begin(),view.end(),false);
		view[SG[i-1]] = true;
		for (int k = 2; k < i; ++k)
			view[SG[i-k] ^ SG[k-1]] = view[SG[i-k] ^ SG[k-2]] = true;
		for (int k = 0; k < SG_MAX; ++k) {
			if (!view[k]) {
				SG[i] = k;
				break;
			}
		}
	}
}

int sg ( int k ) {
	if (k > 72) {
		k -= 72;
		k %= 12;
		k += 72;
	}
	return SG[k];
}

int main() {
	build_sg();
	freopen("bowling.in","rt",stdin);
	freopen("bowling.out","wt",stdout);
	int T = 0,n = 0;
	for (scanf("%d",&T); T; --T) {
		scanf("%d",&n);
		int x = 0, cur = 0;
		for (int i = 0, a; i < n; ++i) {
			scanf("%d",&a);
			if (a == 0) {
				x ^= sg(cur);
				cur = 0;
			} else {
				++cur;
			}
		}
		if (cur != 0)
			x ^= sg(cur);
		if (x)
			printf("Nargy\n"); else
			printf("Fumeanu\n");
	}
	return 0;
}