Cod sursa(job #443386)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 16 aprilie 2010 20:56:46
Problema Bowling Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>

int SG[99],S[99];
char u[99];

int sg(int k)
{
    if (k<=83) return SG[k];
    int i=(k-83)/12;
    if (12*i < k-83) ++i;
    return SG[k-12*i];
}

int main()
{
    freopen("bowling.in","r",stdin);
    freopen("bowling.out","w",stdout);
    int T,N,i,x,j,XS;
    
    for (i=1;i<=83;++i)
    {
        S[0]=0;
        for (j=0;j*2 <= i-1;++j)
            S[++S[0]]=SG[j]^SG[i-1-j];
        for (j=0;j*2 <= i-2;++j)
            S[++S[0]]=SG[j]^SG[i-2-j];
        for (j=0;j<=S[0];++j) u[j]=0;
        for (j=1;j<=S[0];++j) 
            if (S[j]<=S[0]) u[S[j]]=1;
        for (j=0;u[j];++j);
        SG[i]=j;
    }
    
    scanf("%d",&T);
    
    while (T--)
    {
          scanf("%d",&N);
          XS=j=0;
          for (i=0;i<N;++i)
          {
              scanf("%d",&x);
              if (x) ++j;
              else XS^=sg(j),j=0;
          }
          XS^=sg(j);
    
          if (XS != 0) printf("Nargy\n");
          else printf("Fumeanu\n");
    }
        
    return 0;
}