Cod sursa(job #118981)

Utilizator blasterzMircea Dima blasterz Data 28 decembrie 2007 18:29:50
Problema Bowling Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <string>
#define maxn 500

int sg[maxn];
bool use[maxn];

void grundy()
{
  int i, j, n=500;

  sg[0]=0;
  sg[1]=1;
  for(i=2;i<=n;++i)
    {
     
      memset(use, 0, sizeof(use));
      if(i-1>=0) use[sg[i-1]]=1;
      if(i-2>=0) use[sg[i-2]]=1;
      for(j=2;j<i;++j) use[sg[j-1]^sg[i-j]]=1;//, use[sg[i-j]]=1;

      for(j=2;j<i-1;++j) use[sg[j-1]^sg[i-j-1]]=1;//, use[sg[i-j-1]]=1;

      for(j=0;j<=n;++j) if(!use[j]){ sg[i]=j; break;}
    }

  // for(i=0;i<=100;++i) printf("%d:  %d\n", i, sg[i]);




}

void solve()
{
  int i, j, T, n;
  

  freopen("bowling.in","r",stdin);
  freopen("bowling.out","w",stdout);
  scanf("%d\n", &T);

  while(T--)
    {
      memset(use, 0, sizeof(use));
      scanf("%d ", &n);
      for(i=1;i<=n;++i) scanf("%d ", use+i);

      int nr=0, sol=0;
      for(i=1;i<=n;++i)
	if(use[i]==1) ++nr;
	else
	  {
	    sol^=sg[nr];
	    nr=0;
	  }
      if(nr) sol^=sg[nr];

      if(sol==0) printf("Fumeanu\n");
      else printf("Nargy\n");
    }
      
}


int main()
{
  grundy();
   
  solve();

  return 0;
}