Cod sursa(job #7280)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 21 ianuarie 2007 13:18:15
Problema 1-sir Scor 50
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.06 kb
# include <stdio.h>
# include <string.h>

# define  _fin  "1-sir.in"
# define  _fout "1-sir.out"

# define  maxn  515
# define  addn  257
# define  maxs  66000
# define  adds  33000

# define  mod   194767


int n, s, sol;
int ways[2][maxn][maxs];

void readf()
{
	freopen(_fin, "r", stdin);
	scanf("%d %d", &n, &s);
}

void solve()
{
	int i, j, k, crt=0, maxsum;

	ways[crt][0+addn][0+adds] = 1;
	
	for (i=2; i<=n; i++)
	{
		crt=!crt;
		maxsum = (i*(i-1))>>1;

		for (j=-(i-1); j<i; j+=2)
		{
			for (k=-maxsum; k<=maxsum; k+=2)
			{
				if ( (ways[crt][ j+addn ][ k+adds ] = ways[ !crt ][ j+1+addn ][ k-j+adds ]+
												ways[ !crt ][ j-1+addn ][ k-j+adds ]) > mod )
					 ways[crt][ j+addn ][ k+adds ] -= mod;
			}
//			for (k=-maxsum+1; k<maxsum; k+=2)
//				ways[crt][ j+addn ][ k+adds ] = 0;
		}
	}
	
	for (j=-n; j<=n; j++)
		sol = (sol+ways[ crt ][ j+addn ][ s+adds ]) % mod;
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%d\n", sol);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}