Cod sursa(job #39138)

Utilizator vlad_popaVlad Popa vlad_popa Data 26 martie 2007 14:24:39
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <cassert>

#define FIN "bowling.in"
#define FOUT "bowling.out"
#define NMAX 50001

int min[NMAX], grundy[NMAX], iter, N, T;

void preproc ()
{
  int sum;
  
  grundy[1] = 1;
  
  for (int i = 2; i <= 83; ++ i)
   {
     ++ iter;
     min[grundy[i-1]] = min[grundy[i-2]] = iter;

     sum = i - 1;
     for (int j = 1; j <= sum / 2; ++ j)
       min[(grundy[j] ^ grundy[(sum - j)])] = iter;

     sum = i - 2;
     for (int j = 1; j <= sum / 2; ++ j)
       min[(grundy[j] ^ grundy[(sum - j)])] = iter;

     for (int j = 0; j <= 10; ++ j)
       if (min[j] != iter)
        {
          grundy[i] = j;
          break;
        }
   }

  for (int i = 84; i <= 50000; ++ i)
    grundy[i] = grundy[i - 12];
}

void solve ()
{
  int sol, popica, ct;
  
  scanf ("%d", &T);

  while (T--)
   {
     scanf ("%d", &N);

     sol = ct = 0;
     for (int i = 1; i <= N; ++ i)
      {
        scanf ("%d", &popica);
        if (popica)
          ++ ct;
        else
         {
           sol ^= grundy[ct];
           ct = 0;
         }
      }
     sol ^= grundy[ct];
     if (sol)
       printf ("Nargy\n");
     else
       printf ("Fumeanu\n");
   }
}

int
 main ()
{
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  preproc ();
  solve ();

  return 0;
}