Cod sursa(job #1953480)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 aprilie 2017 20:49:08
Problema Bowling Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

const int nMAX = 500 + 5;

int t;
int n;
int S[nMAX];
bool reach[nMAX];

int getMex() {
    int i = 0;
    while (reach[i] == true)
        i++;
    return i;
}

void calcSpragueGrundy() {
    S[0] = 0;
    S[1] = 1;
    for (int i = 2; i < nMAX; i++) {
        memset(reach, false, sizeof reach);
        for (int j = 1; j <= i; j++) {
            reach[S[j - 1] ^ S[i - j]] = true;
            if (j < i) reach[S[j - 1] ^ S[i - j - 1]] = true;
        }
        S[i] = getMex();
    }
}

int main() {
    freopen("bowling.in", "r", stdin);
    freopen("bowling.out", "w", stdout);

    calcSpragueGrundy();

    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int xorSum = 0;
        int v = 0;
        int c = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &v);
            if (v == 1) c++;
            else {
                xorSum ^= S[c];
                c = 0;
            }
        }
        xorSum ^= S[c];
        if (xorSum == 0) puts("Fumeanu");
        else puts("Nargy");
    }
}