Cod sursa(job #986744)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 19 august 2013 14:46:31
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>

#define NMax 50005

using namespace std;

int N, SG[NMax], SumSG;
bitset <NMax> H;
char Name[2][8]={"Fumeanu", "Nargy"};

inline int MEX (vector <int> &M)
{
    for (vector <int> :: iterator X=M.begin (); X!=M.end (); ++X)
    {
        H[*X]=1;
    }
    int SX;
    for (SX=0; H[SX]; ++SX);
    for (vector <int> :: iterator X=M.begin (); X!=M.end (); ++X)
    {
        H[*X]=0;
    }
    return SX;
}

void BuildSG ()
{
    SG[0]=0;
    for (int i=1; i<=84; ++i)
    {
        vector <int> M;int end=(i/2)+1;
        for (int j=1; j<=end; ++j)
        {
            M.push_back (SG[j-1]^SG[i-j]);
            M.push_back (SG[j-1]^SG[i-j-1]);
        }
        SG[i]=MEX (M);
    }
}

inline int Period (int X)
{
    if (X<72)
    {
        return X;
    }
    return 72+(X-72)%12;
}

void Read ()
{
    scanf ("%d", &N);
    int Length=0;
    SumSG=0;
    for (int i=1; i<=N; ++i)
    {
        int X;
        scanf ("%d", &X);
        if (X)
        {
            ++Length;
        }
        else
        {
            SumSG^=SG[Period (Length)];
            Length=0;
        }
    }
    if (Length>0)
    {
        SumSG^=SG[Period (Length)];
        Length=0;
    }
}

void Print ()
{
    if (SumSG!=0)
    {
        SumSG=1;
    }
    printf ("%s\n", Name[SumSG]);
}

int main()
{
    freopen ("bowling.in", "r", stdin);
    freopen ("bowling.out", "w", stdout);
    BuildSG ();
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        Read ();
        Print ();
    }
    return 0;
}