Cod sursa(job #1365638)

Utilizator retrogradLucian Bicsi retrograd Data 28 februarie 2015 13:57:25
Problema Bowling Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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) {
    memset(C, 0, sizeof(C));
    if(COMP[n]) {
        return SG[n];
    }

    for(var i=1; i<=2; i++) {
        for(var a=0; a<=n-i; a++) {
            C[sparge_grundy(a)^sparge_grundy(n-a-i)] = 1;
        }
    }

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





int main() {

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

    fin>>t;

    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 ^= sparge_grundy(v);
        }

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

    }
    return 0;
}