Cod sursa(job #7724)

Utilizator gcosminGheorghe Cosmin gcosmin Data 22 ianuarie 2007 09:35:41
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <string.h>

#define OF 33000
#define MOD 194767
#define XMAX 70000

int N, S;

int ant[XMAX];
int cur[XMAX];

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

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

	int smax = N * (N - 1) / 2;

	if (S > smax || S < -smax) {
		printf("0\n");
		return 0;
	}

	ant[smax + OF] = cur[smax + OF] = 1;
	ant[smax + OF - 2] = cur[smax + OF - 2] = 1;

	for (i = N - 2; i >= 0; i--) {

		for (s = -smax; s <= smax; s++) {
			cur[s + OF] += s + OF + 2 * (N - i) < XMAX ? ant[s + OF + 2 * (N - i)] : 0;
			if (cur[s + OF] >= MOD) s[cur + OF] -= MOD;
		}

		memcpy(ant, cur, sizeof(cur));	
	}

//	for (s = -smax; s <= smax; s++) printf("%d %d\n", s, cur[s + OF]);

	printf("%d\n", cur[S + OF]);


fclose(stdin);
fclose(stdout);
return 0;
}