Cod sursa(job #271732)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 martie 2009 21:38:14
Problema Bowling Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

#define maxN 50010
vector<int> T;
int V[maxN], A[maxN];

void precalc() {
	int i, j, left, right, min;
	V[0] = 0;
	
	for (i = 1; i <= 500; ++ i) {
		T.clear(); min = 0;
		for (j = 1; j <= i; ++ j){
			left = j - 1;
			right = i - j;
			T.push_back(V[left] ^ V[right]);
			if (j < i){
				left = j- 1;
				right = i - j - 1;
				T.push_back(V[left] ^ V[right]);
			}
		}
		sort(T.begin(), T.end());
		for (j = 0; j < T.size(); ++ j)
			if (T[j] == min)	 ++ min;
		V[i] = min;
	}
	//for (i = 72; i <= 100; ++ i)
	//	printf("%d ", V[i]);
}

int sol(int x){
	if (x < 72)	return V[x];
	else return V[72 + x % 12];
}
int main(){
	int i, j, t, comp, Sum, N, now;

	freopen("bowling.in", "r", stdin);
	freopen("bowling.out", "w", stdout);
	
	precalc();
	for (scanf("%d", &t); t --; ){
		for (scanf("%d", &N), i = 1; i <= N; ++ i)	scanf("%d", &A[i]);
		if (A[1]) comp = 1;
		else	comp = 0;
		 Sum = 0;
		for (i = 2; i <= N + 1; ++ i)
			if (i == N + 1 || A[i] == 0){
				if (A[i - 1] == 1){
					now = sol(comp);
					Sum ^= now;
					comp = 0;
				}
			}
			else	comp ++;
		if (Sum)	puts("Nargy");
		else		puts("Fumeanu");
	}
	//for (i = 1; i <= 72; ++ i)
	//	printf("%d ", V[i]);
}