Cod sursa(job #1988631)

Utilizator mariakKapros Maria mariak Data 3 iunie 2017 20:06:23
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

FILE *fin  = freopen("bowling.in", "r", stdin);
FILE *fout = freopen("bowling.out", "w", stdout);

using namespace std;

const int maxN = 5e4 + 2;
int T;
int mex[100];
char s[maxN];
int v[1000];
bool vis[100];

int Sg(int x){
    if(x < 3) return x;
    else if(vis[x]) return mex[x];
    else{
        vis[x] = 1;
        int len = 0;
        v[len ++] = Sg(x - 1), v[len ++] = Sg(x - 2);
        for(int i = 1; i < x - 1; ++ i)
            v[len ++] = Sg(i) ^ Sg(x - i - 1);
        for(int i = 1; i < x - 2; ++ i)
            v[len ++] = Sg(i) ^ Sg(x - i - 2);
        sort(v, v + len);
        if(v[0] != 0){
            mex[x] = 0;
            return 0;
        }
        for(int i = 0; i < len; ++ i)
                if(v[i + 1] > v[i] + 1){
                    mex[x] = v[i] + 1;
                    return mex[x];
                }
        mex[x] = v[len - 1] + 1;
        return mex[x];
    }
}

int sg(int x){
    if(x <= 72)
        return mex[x];
    else return mex[72 + x%12];
}

int main(){
    for(int i = 0; i <= 85; ++ i)
        mex[i] = Sg(i);

    scanf("%d", &T);
    while(T --){
        int n; scanf("%d", &n);
        int len = 0, ans = 0;
        for(int i = 0; i < n; ++ i){
            int x; scanf("%d", &x);
            if(x)
                ++ len;
            else{
                ans ^= sg(len);
                len = 0;
            }
        }
        if(len) ans ^= sg(len);
        if(ans)
            printf("Nargy\n");
        else
            printf("Fumeanu\n");
    }
    return 0;
}