Cod sursa(job #39381)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 26 martie 2007 18:05:28
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
# include <stdio.h>
# include <string.h>

# define  _fin	"bowling.in"
# define  _fout "bowling.out"

# define  maxn	50505
# define  maxsg 50005

int sg[maxn], viz[13];

void presolve()
{
	int i, j;
	sg[0]=0,sg[1]=1,sg[2]=2;
	
	for (i=3; i<84; i++)
	{
		memset(viz, 0, sizeof(viz));
		viz[ sg[i-1] ] = viz[ sg[i-2] ] = 1;
		for (j=2; j<i; j++)	// luam una
			viz[ sg[j-1]^sg[i-j] ] = 1;
		for (j=2; j<i-1; j++)
			viz[ sg[j-1]^sg[i-j-1] ] = 1;
		for (j=0; j<maxn; j++)
			if ( !viz[j] ) {
				sg[i]=j;
				break;
			}
	}
	for (i=84; i<maxsg; i+=12)
		for (j=0; j<12; j++) sg[i+j]=sg[72+j];
}

int main()
{
	int t, n, i, j, sgv=0, sum=0, x;
	presolve();
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	
	for (scanf("%d", &t); t; --t) {
		for (scanf("%d", &n), sum=sgv=0, i=1; i<=n; i++) {
			scanf("%d", &x);
			if ( x ) ++sum;
			else sgv=sgv^sg[sum], sum=0;
		}
		sgv=sgv^sg[sum];
		printf("%s\n", sgv?"Nargy":"Fumeanu");
	}
	
	return 0;
}