Cod sursa(job #6930)

Utilizator MariusMarius Stroe Marius Data 21 ianuarie 2007 10:55:36
Problema 1-sir Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.08 kb
#include <cstdio>
using namespace std;

const char iname[] = "1-sir.in";
const char oname[] = "1-sir.out";

#define MAX_N  77
#define lim    MAX_N * MAX_N
#define modulo 194767

int cnt[2][MAX_N * MAX_N * 2][MAX_N * 2];

int main(void) {
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	int N;
	int S;
	scanf("%d %d", & N, & S);
	if ((2 * S > N * (N - 1)) || (2 * S < - N * (N - 1))) {
		printf("0\n");
		return 0;
	}
	if ((N & 1) && (S & 1)) {
		printf("0\n");
		return 0;
	}
	if ((N % 2 == 0) && (S % 2 == 0)) {
		printf("0\n");
		return 0;
	}
	int step = 0;
	cnt[step][lim][MAX_N] = 1;
	for (int i = step = 1; i < N; ++i) {
		int li = -i*(i+1)/2;
		int ls = +i*(i+1)/2;
		for (int j = li; j <= ls; ++j)
			for (int k = -i; k <= +i; ++k)
				cnt[step][j + lim][k + MAX_N] = (cnt[1 ^ step][j - k + lim][k - 1 + MAX_N] + 
												 cnt[1 ^ step][j - k + lim][k + 1 + MAX_N]) % modulo;
		step ^= 1;
	}
	int Res = 0;
	for (int k = -N; k <= +N; ++k) 
		Res = (Res + cnt[1 ^ step][S + lim][k + MAX_N]) % modulo;
	printf("%d\n", Res);
	return 0;
}