Cod sursa(job #2928979)

Utilizator lolismekAlex Jerpelea lolismek Data 24 octombrie 2022 12:44:07
Problema Bowling Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>

using namespace std;

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

const int NMAX = 500;
int sg[NMAX + 5];
bool f[NMAX + 5];

int MEX(vector <int> v){
	for(int i = 0; i <= NMAX + 4; i++)
		f[i] = 0;

	int maxi = 0;
	for(auto x : v)
		f[x] = true;

	for(int val = 0; val <= NMAX; val++)
		if(!f[val])
			return val;
}

// x <- (i, x - i - 1) ^ (i, x - i - 2)
void spragueGrundy(){
	sg[0] = 0;
	for(int i = 1; i <= NMAX; i++){
		vector <int> v;
		for(int j = 1; j <= i; j++){
			if(j < i)
				v.push_back(sg[j - 1] ^ sg[i - j - 1]);
			v.push_back(sg[j - 1] ^ sg[i - j]);
		}

		sg[i] = MEX(v);
	}
}

string players[] = {"Fumeanu", "Nargy"};
void solve(){

	int n;
	fin >> n;

	int len = 0, xorSum = 0;
	for(int i = 1; i <= n; i++){
		int x;
		fin >> x;

		if(x == 1)
			len++;
		else
			xorSum ^= len, len = 0;
	}
	xorSum ^= len;

	fout << players[(xorSum != 0)] << '\n'; 
}

int main(){

	spragueGrundy();

	int T;
	fin >> T;

	while(T--)
		solve();

	return 0;
}