Cod sursa(job #926850)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 25 martie 2013 13:30:08
Problema Bowling Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<iostream>
#include<cstdio>
using namespace std;

const int N = 51000;

int n, d[N];

void sol() {
    int i, sz = 0, t, sol = 0;
    cin >> n;

    for(i = 1; i <= n; ++i) {
        cin >> t;
        if(t)
            ++sz;
        else {
            sol ^= d[sz];
            sz = 0;
        }
    }
    sol ^= d[sz];

    cout << (sol ? "Nargy\n" : "Fumeanu\n");
}

void precalc() {
    int i, j, ver[10];
    d[1] = 1;

    for(i = 2; i <= 50000; ++i) {
        for(j = 0; j < 10; ++j)
            ver[j] = 0;

        int p1 = (i - 1) / 2, p2 = (i - 1) / 2;
        if((i - 1) & 1)
            ++p2;

        for(j = 1; j <= 20; ++j) {
            if((d[p1] ^ d[p2]) < 10)
                ver[d[p1] ^ d[p2]] = 1;

            --p1;
            ++p2;
        }

        p1 = (i - 2) / 2, p2 = (i - 2) / 2;
        if((i - 2) & 1)
            ++p2;
        for(j = 1; j <= 20; ++j) {
            if((d[p1] ^ d[p2]) < 10)
                ver[d[p1] ^ d[p2]] = 1;

            --p1;
            ++p2;
        }

        for(j = 0; j < 10; ++j) if(!ver[j]) {
            d[i] = j;
            break;
        }
    }
}

int main() {

    freopen("bowling.in", "r", stdin);
    freopen("bowling.out", "w", stdout);
    int t;
    cin >> t;
    precalc();

    while(t--)
        sol();

    return 0;
}