Cod sursa(job #2018720)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 5 septembrie 2017 18:54:33
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
#define NMAX 50010
using pii = pair<int, int>;

int mex[NMAX];

int getMex(vector<int> v)
{
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	int i;
	for(i = 0; i < v.size() && v[i] == i; ++i);
	return i;
}

int main()
{
	freopen("bowling.in", "r", stdin);
	freopen("bowling.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	
	int t, i, j, n, ans, nr, a;
	
	for(i = 1; i <= 100; ++i)
	{
		vector<int> v;
		
		for(j = 0; j < i; ++j)
		{
			v.push_back(mex[j] ^ mex[i - j - 1]);
			if(i - j - 2 >= 0) v.push_back(mex[j] ^ mex[i - j - 2]);
		}
		
		mex[i] = getMex(v);
	}
	
	for(i = 101; i <= 50000; ++i)
		mex[i] = mex[i - 12];
	
	for(cin >> t; t; --t)
	{
		cin >> n;
		
		for(ans = 0, nr = 0, i = 1; i <= n; ++i)
		{
			cin >> a;
			
			if(a == 1) ++nr;
			if(a == 0 || i == n)
				ans ^= mex[nr], nr = 0;
		}
		
		cout << (ans == 0 ? "Fumeanu\n" : "Nargy\n");
	}
	
	return 0;
}