Cod sursa(job #992888)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 2 septembrie 2013 18:32:28
Problema Bowling Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb

#include <cstdio>
#include <bitset>

const int MAX_SIZE(100);
const int MAX_N(84);

int Value [MAX_N + 1];
std::bitset<MAX_SIZE> Mark;

inline int MinimumExcludedValue (void)
{
	for (int i(0) ; i < MAX_SIZE ; ++i)
		if (!Mark[i])
			return i;
	return MAX_SIZE + 1;
}

inline void SpragueGrundy (void)
{
	Value[1] = 1;
	int i, j, end;
	for (i = 2 ; i <= MAX_N ; ++i)
	{
		for (j = 1, end = (i >> 1) + 1 ; j <= end ; ++j)
			Mark[Value[i - j] ^ Value[i - (i - j) - 1]] = Mark[Value[i - j - 1] ^ Value[i - (i - j) - 1]] = true;
		Value[i] = MinimumExcludedValue();
		Mark.reset();
	}
}

inline int Period (int x)
{
	if (x <= MAX_N)
		return x;
	x %= MAX_N;
	if (!x)
		return MAX_N;
	return 72 + x;
}

inline void Query (void)
{
	int n, x, game(0), sum(0);
	std::scanf("%d",&n);
	while (n)
	{
		std::scanf("%d",&x);
		if (x)
			++game;
		else
		{
			sum ^= Value[Period(game)];
			game = 0;
		}
		--n;
	}
	sum ^= Value[Period(game)];
	std::printf("%s\n",(sum ? "Nargy" : "Fumeanu"));
}

int main (void)
{
	SpragueGrundy();
	std::freopen("bowling.in","r",stdin);
	std::freopen("bowling.out","w",stdout);
	int t;
	std::scanf("%d",&t);
	while (t)
	{
		Query();
		--t;
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}