Cod sursa(job #1496911)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 5 octombrie 2015 19:37:28
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <bitset>

using namespace std;

int dp[505];

bitset <505> vis;

inline void brut_dp () {
    dp[1] = 1;
    dp[2] = 2;

    int j;
    for (int i = 3; i <= 500; ++ i) {
        vis &= 0;
        for (j = 0; j < i; ++ j)
            vis[dp[j] ^ dp[i - j - 1]] = 1;
        for (j = 0; j < i - 1; ++ j)
            vis[dp[j] ^ dp[i - j - 2]] = 1;

        for (j = 0; j < 505; ++ j)
            if (!vis[j]) {
                dp[i] = j;
                break;
            }

        //cout << i << ' ' << dp[i];
        //if (i >= 88)
        //    cout << ' ' << (dp[i] == dp[i - 12]) << endl;
        //else
        //    cout << endl;
    }
}

inline int get_sp (int n) {
    if (n <= 88)
        return dp[n];
    else
        return dp[88 + (n - 88) % 12];
}

const int NMAX = 50005;
bool sir[NMAX];

int main()
{
    ifstream cin("bowling.in");
    ofstream cout("bowling.out");

    brut_dp();

    int t = 0;
    cin >> t;

    while (t --) {
        int n = 0;
        int ans = 0;

        cin >> n;
        for (int i = 1; i <= n; ++ i)
            cin >> sir[i];

        int current = 0;
        for (int i = 1; i <= n; ++ i)
            if (sir[i])
                ++ current;
            else {
                ans ^= get_sp(current);
                current = 0;
            }

        ans ^= get_sp(current);

        if (ans)
            cout << "Nargy\n";
        else
            cout << "Fumeanu\n";
    }

    cin.close();
    cout.close();
    return 0;
}