Cod sursa(job #184781)

Utilizator tm_raduToma Radu tm_radu Data 24 aprilie 2008 12:11:00
Problema Bowling Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#define NM 50010

int n, m, t;
int a[NM], sg[NM], s[NM];
int i, j, k, l, sxor;

int SG(int l);

int main()
{
	freopen("bowling.in", "r", stdin);
	freopen("bowling.out", "w", stdout);
	for ( i = 0; i <= NM-1; sg[i] = -1, i++ );
	scanf("%d", &t);
	while ( t )
	{
	    t--;
	    k = l = 0; scanf("%d", &n);
	    for ( i = 1; i <= n; i++ )
	    {
	         scanf("%d", &j);
	         if ( j == 1 ) l++;
	         else          k++, a[k] = l, l = 0;
	    }
	    if ( l ) k++, a[k] = l;
	    sxor = 0;
        for ( i = 1; i <= k; i++ )
             sxor = sxor ^ SG(a[i]);     
	    if ( sxor == 0 ) printf("Fumeanu\n");
	    else             printf("Nargy\n");
	}    
    return 0;
}

int SG(int l)
{
	if ( l == 0 ) return sg[0] = 0;
	if ( l == 1 ) return sg[1] = 1;
	if ( sg[l] != -1 ) return sg[l];
	int i;
	for ( i = 0; i <= l; s[i] = 0, i++ );
	for ( i = 0; i <= l-2; i++ )
		s[SG(i)^SG(l-i-2)] = 1;
	for ( i = 0; i <= l-1; i++ )
		s[SG(i)^SG(l-i-1)] = 1;
	for ( i = 0; i <= l+1; i++ )
		if ( s[i] == 0 ) break;
	return sg[l] = i;
}