Cod sursa(job #7278)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 21 ianuarie 2007 13:17:43
Problema 1-sir Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 0.77 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 260
#define SMAX 66000
#define SZERO 33000
#define P 194767

#define T(x,sum) ns[x][sum + SZERO]

int ns[2][SMAX];
int i, j, k, N, S, c, a, Smax[NMAX];

int main()
{
	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);

	scanf("%d %d", &N, &S);

	Smax[1] = 0;
	for (i = 2; i <= N; i++)
		Smax[i] = Smax[i - 1] + (i - 1);

	if (abs(S) > Smax[N])
	{
		printf("0\n");
		return 0;
	}

	memset(ns, 0, sizeof(ns));

	c = 0;
	T(c, 0) = 1;

	for (i = 2; i <= N; i++)
	{
		a = c;
		c = 1 - c;

		for (j = 0; j <= Smax[i]; j++)
		{
			T(c, j) = (T(a, j - i + 1) + T(a, j + i - 1)) % P;
			T(c, -j) = T(c, j);
		}
	}

	printf("%d\n", T(c, S));

	return 0;
}