Cod sursa(job #1799182)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 5 noiembrie 2016 21:25:15
Problema Bowling Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <algorithm>

int real[1000], viz[1000];

int solve(int n){
    if(n<=0) return 0;
    if(viz[n]) return real[n];
    viz[n]=1;
    if(n==1) real[n]=1;
    else if(n==2) real[n]=2;
    else{
        int k=0, v[1000];
        v[k++]=solve(n-1);
        v[k++]=solve(n-2);
        for(int i=1; i<=n-2; i++)
            v[k++]=solve(i)^solve(n-i-1);
        for(int i=1; i<=n-3; i++)
            v[k++]=solve(i)^solve(n-i-2);
        std::sort(v, v+k);
        if(v[0]!=0) real[n]=0;
        else{
            for(int i=1; i<k; i++){
                if(v[i-1]+1<v[i]){
                    real[n]=v[i-1]+1;
                    return real[n];
                }
            }
            real[n]=v[k-1]+1;
        }
    }
    return real[n];
}

int main(){
    int t, poz, per;
    FILE *fin, *fout;
    fin=fopen("bowling.in", "r");
    fout=fopen("bowling.out", "w");
    for(int i=1; i<=300; i++) real[i]=solve(i);
    poz=97;
    per=7;
    for(fscanf(fin, "%d", &t); t; t--){
        int n;
        fscanf(fin, "%d", &n);
        int sc=0;
        int ans=0;
        for(int i=1; i<=n; i++){
            int x;
            fscanf(fin, "%d", &x);
            if(x==1) sc++;
            else{
                if(sc<poz) ans^=real[sc];
                else ans^=real[poz+(sc-poz)%per];
                sc=0;
            }
        }
        if(sc<poz) ans^=real[sc];
        else ans^=real[poz+(sc-poz)%per];
        if(ans==0) fprintf(fout, "Fumeanu\n");
        else fprintf(fout, "Nargy\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}