Cod sursa(job #7029)

Utilizator IgnitionMihai Moraru Ignition Data 21 ianuarie 2007 11:55:10
Problema 1-sir Scor 10
Compilator c Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 0.98 kb
#include <stdio.h>
#include <string.h>

#define MN (200)
#define MS (10001)

/*
#define MN (20)
#define MS (101)
*/

int oldc[MN][MS], newc[MN][MS];
int N, S, X;
const int mod = 194767;

int main()
{
	int n, s, k;
	int smin, smax, kmid, smid;

	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);
	
	/*
	double size = sizeof(oldc)+sizeof(newc);
	printf("%.4lf\n", size/1024/1024);
	return 0;
	*/
	
	scanf("%d %d", &N, &S);
	//printf("%d %d\n", N, S);
	
	if((N*(N-1)/2)%2 != S%2) {
		printf("0\n");
		return 0;
	}
	
	kmid = N; smid = N*(N+1)/2;
	oldc[kmid][smid] = 1;
	for(n = 2; n <= N; ++ n) {
		smin = -n*(n-1)/2; smax = -smin;
		for(s = smin; s <= smax; ++ s)
			for(k = -n+1; k <= n-1; ++ k) {
				newc[kmid+k][smid+s] = oldc[kmid+k-1][smid+s-k];
				newc[kmid+k][smid+s] += oldc[kmid+k+1][smid+s-k];
				newc[kmid+k][smid+s] %= mod;
			}
		memcpy(oldc, newc, sizeof(oldc));
	}

	for(k = -N+1; k <= N-1; ++ k)
		X += oldc[kmid+k][smid+S], X %= mod;
	printf("%d\n", X);
	
	return 0;
}