Cod sursa(job #994833)

Utilizator primulDarie Sergiu primul Data 6 septembrie 2013 14:19:37
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <bitset>
 
const int MAX_SIZE(100);
const int MAX_N(84);
 
int Value [MAX_N + 1];
std::bitset<MAX_SIZE> Mark;
 
inline int MinimumExcludedValue (void)
{
    for (int i(0) ; i < MAX_SIZE ; ++i)
        if (!Mark[i])
            return i;
    return MAX_SIZE + 1;
}
 
inline void SpragueGrundy (void)
{
    Value[1] = 1;
    int i, j, end;
    for (i = 2 ; i <= MAX_N ; ++i)
    {
        for (j = 1, end = (i >> 1) + 1 ; j <= end ; ++j)
            Mark[Value[i - j] ^ Value[i - (i - j) - 1]] = Mark[Value[i - j - 1] ^ Value[i - (i - j) - 1]] = true;
        Value[i] = MinimumExcludedValue();
        Mark.reset();
    }
}
 
inline int Period (int x)
{
    if (x < 72)
        return x;
    return (x - 72) % 12 + 72;
}
 
inline void Query (void)
{
    int n, x, game(0), sum(0);
    std::scanf("%d",&n);
    while (n)
    {
        std::scanf("%d",&x);
        if (x)
            ++game;
        else
        {
            sum ^= Value[Period(game)];
            game = 0;
        }
        --n;
    }
    sum ^= Value[Period(game)];
    std::printf("%s\n",(sum ? "Nargy" : "Fumeanu"));
}
 
int main (void)
{
    SpragueGrundy();
    std::freopen("bowling.in","r",stdin);
    std::freopen("bowling.out","w",stdout);
    int t;
    std::scanf("%d",&t);
    while (t)
    {
        Query();
        --t;
    }
    std::fclose(stdin);
    std::fclose(stdout);
    return 0;
}