Cod sursa(job #1365711)

Utilizator retrogradLucian Bicsi retrograd Data 28 februarie 2015 14:37:46
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<fstream>
#include<vector>
#include<cstring>

using namespace std;
typedef int var;

ifstream fin("bowling.in");
ofstream fout("bowling.out");

vector<var> V;
var SG[50002];
bool COMP[50002];
bool C[50002];


var sparge_grundy(var n) {

    if(COMP[n]) {
        return SG[n];
    }
    memset(C, 0, sizeof(C));
    for(var i=1; i<=2; i++) {
        for(var a=0; a<=n-i; a++) {
            C[SG[a]^SG[n-a-i]] = 1;
        }
    }

    var i;
    for(i=0; C[i] == 1; i++);
    SG[n] = i;
    COMP[n] = 1;
    return SG[n];
}

var sg(var n) {
    while(n>900) n-=36;
    return SG[n];
}





int main() {

    var n, t;
    bool b;
    COMP[0] = 1;
    COMP[1] = 1;
    SG[1] = 1;

    fin>>t;

    for(var i=0; i<=1000; i++) {
        sparge_grundy(i);
    }

    while(t--) {
        fin>>n;
        var nr = 0;
        V.clear();
        for(var i=1; i<=n; i++) {
            fin>>b;
            if(b == 1) {
                nr++;
            } else {
                if(nr)
                    V.push_back(nr);
                nr = 0;
            }
        }
        if(nr) {
            V.push_back(nr);
        }

        var rez = 0;
        for(auto v : V) {
            rez ^= sg(v);
        }

        if(rez == 0) {
            fout<<"Fumeanu\n";
        } else {
            fout<<"Nargy\n";
        }

    }
    return 0;
}