Cod sursa(job #606760)

Utilizator crushackPopescu Silviu crushack Data 9 august 2011 22:19:54
Problema Bowling Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <bitset>
#define NMax 50010
#define LMax 84
using namespace std;

const char IN[]="bowling.in",OUT[]="bowling.out";
const char nume[][8]= { "Fumeanu" , "Nargy"};
int Tes,N,Rez;
int a[NMax];
int SG[LMax];

int get(int x){
	return x<72 ? SG[x] : SG[72 + (x-72)%12];
}

void init()
{
	int i,j;
	bitset<10> b;
	SG[0]=0;
	for (i=1;i<84;++i)
	{
		b.reset();
		for (j=1;j<=i;++j)
		{
			b[ SG[j-1]^SG[i-j] ]=true;
			if (j<i)
				b[ SG[j-1]^SG[i-j-1] ]=true;
		}
		for (j=0;b[j];++j);SG[i]=j;
	}
}

int main()
{
	int i,j;
	init();
	
	freopen(IN,"r",stdin);
	scanf("%d",&Tes);
	
	freopen(OUT,"w",stdout);
	while (Tes--)
	{
		scanf("%d",&N);
		for (i=1;i<=N;++i) scanf("%d",a+i);
		
		j=0;Rez=0;a[0]=-2;
		for (i=1;i<N;++i)
		{
			if (a[i]==a[i-1])
				++j;
			else
			{
				if (a[i-1]==1) Rez^=get(j);
				j=a[i];
			}
		}
		Rez^=get(j);
		printf("%s\n",Rez ? nume[1] : nume[0]);
	}
	fclose(stdout);
	fclose(stdin);
	return 0;
}