Cod sursa(job #2611355)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 6 mai 2020 19:03:23
Problema Bowling Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
std::ifstream fin ("bowling.in");
std::ofstream fout ("bowling.out");



int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie (NULL);
    std::cout.tie (NULL);

    int sg[500005];
    sg[0] = 0;
    /*

    for (int i=1, j; i<=10000; i++){
        std::unordered_set < int > s;
        for (j=0; j<=i/2; j++){
            s.insert (sg[j] ^ sg[i-j-1]);
            //std::cout<< (sg[j] ^ sg[i-j-1]) << ' ';
        }

        for (j=0; j<=(i-1)/2; j++){
            s.insert (sg[j] ^ sg[i-j-2]);
            //std::cout << (sg[j] ^ sg[i-j-2]) << ' ';
        }


        for (j=0; s.find(j) != s.end(); j++);

        sg[i] = j;
        //std::cout << '\n';
    }
    for (int i=0; i<=10000; i++)
        fout << sg[i] << ' ';
    fout << '\n';
    */

    for (int i=1, j; i<=10000; i++){
        std::unordered_set < int > s;
        for (j=0; j<i and j <= 40; j++){
            s.insert (sg[j] ^ sg[i-j-1]);
            //std::cout<< (sg[j] ^ sg[i-j-1]) << ' ';
        }

        for (j=0; j<i-1 and j <= 40; j++){
            s.insert (sg[j] ^ sg[i-j-2]);
            //std::cout << (sg[j] ^ sg[i-j-2]) << ' ';
        }


        for (j=0; s.find(j) != s.end(); j++);

        sg[i] = j;
        //std::cout << '\n';
    }

    //for (int i=0; i<=50000; i++)
    //    fout << sg[i] << ' ';

    int Q;
    fin >> Q;
    while (Q--){
        int n, i, lung;
        fin >> n;
        bool x[n];
        std::vector < int > arr;

        for (i=0; i<n; i++)
            fin >> x[i];

        if (x[0] == 1)
            lung = 1;
        else
            lung = 0;
        for (i=1; i<n; i++){
            if (x[i] == 1)
                lung ++;
            else{
                if (lung)
                    arr.push_back (lung);
                lung = 0;
            }
        }
        if (lung)
            arr.push_back (lung);

        int grundy = 0;
        for (i=0; i<arr.size(); i++)
            grundy = grundy ^ sg[arr[i]];

        if (grundy == 0)
            fout << "Fumeanu\n";
        else
            fout << "Nargy\n";

    }

    return 0;
}