Cod sursa(job #44650)

Utilizator wefgefAndrei Grigorean wefgef Data 31 martie 2007 16:54:33
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define sz size()
#define all(v) v.begin(), v.end()
#define pb push_back

int sg[101];
vector<int> v;

int mex(int n)
{
	int st, dr, i, rez = 0;
	
	v.clear();
	for (i = 1; i <= n; ++i)
		v.pb(sg[i-1] ^ sg[n-i]);
	for (i = 2; i <= n; ++i)
		v.pb(sg[i-2] ^ sg[n-i]);
	sort(all(v));
	
	for (i = 0; i < v.sz; ++i)
		if (v[i] > rez) return rez; else
		if (v[i] == rez) ++rez;
	return rez;
}

void preproc()
{
	for (int i = 1; i <= 100; ++i)
		sg[i] = mex(i);
}

int SG(int n)
{
	int r;
	
	if (n <= 100) return sg[n];
	r = (n-100)/12;
	n -= r*12;
	while (n > 100) n -= 12;
	
	return sg[n];
}

int main()
{
	freopen("bowling.in", "r", stdin);
	freopen("bowling.out", "w", stdout);
	
	int i, rez, n, cur, val, t;
	
	preproc();
	for (scanf("%d", &t); t; --t)
	{
		scanf("%d", &n);
		cur = rez = 0;
		for (i = 1; i <= n; ++i)
		{
			scanf("%d", &val);
			if (val == 1) ++cur;
			else
			{
				rez ^= SG(cur);
				cur = 0;
			}
		}
		rez ^= SG(cur);
		if (rez) printf("Nargy\n");
		else printf("Fumeanu\n");
	}
	
	return 0;
}