Cod sursa(job #38336)

Utilizator astronomyAirinei Adrian astronomy Data 25 martie 2007 18:03:12
Problema Bowling Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <string.h>

#define MAXN (1 << 16)

const int grundy[] = {7, 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2};

int N, A[72][72], conf[72];
int T[MAXN];

int baga(int i, int j)
{
    int k, t;
    char uz[16];

    if(i > j)
        return 0;
        
    if(A[i][j] != -1)
        return A[i][j];

    memset(uz, 0, sizeof(uz));


    for(k = i; k <= j; k++)
    {
        t = baga(i, k-1) ^ baga(k+1, j);
        uz[t] = 1;
    }

    for(k = i; k+1 <= j; k++)
    {
        t = baga(i, k-1) ^ baga(k+2, j);
        uz[t] = 1;
    }

    for(t = 0; t < 1024; t++)
     if(!uz[t])
     {
        A[i][j] = t;
        break ;
     }

    return t;
}

void preproc(void)
{
    for(N = 1; N <= 70; N++)
    {
        memset(A, -1, sizeof(A));
        conf[N] = baga(1, N);
    }
}

int solve(void)
{
    int i, t = 0, gr, len;

    for(T[++N] = 0, i = 1, len = 0; i <= N; i++)
    {
        if(T[i] == 1)
            len++;
        else
        {
            if(len <= 70)
                gr = conf[len];
            else
                gr = grundy[(len-70-1)%12];
            t ^= gr, len = 0;
        }
    }

    if(t == 0)
        return 0;

    return 1;
}

void ruleaza(void)
{
    int i, teste;

    scanf("%d\n", &teste);

    preproc();
    
    while(teste--)
    {
        scanf("%d ", &N);
        for(i = 1; i <= N; i++)
            scanf("%d ", &T[i]);
        printf("%s\n", solve() ? "Nargy" : "Fumeanu");
    }
}

int main(void)
{
    freopen("bowling.in", "rt", stdin);
    freopen("bowling.out", "wt", stdout);

    ruleaza();

    return 0;
}