Cod sursa(job #220462)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 10 noiembrie 2008 22:31:11
Problema 1-sir Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>

const int N_MAX = 33000;
const int MOD = 194767;

int nrmod[N_MAX];

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

	int N, S;
	scanf("%d %d\n", &N, &S);
	S = (N * (N - 1) / 2) - S;
	if (S < 0) {
		printf("0\n");
		return 0;
	}

	int MAX = 0, fac, mx;
	nrmod[0] = 1;
	for (int j = 1; j < N; j ++) {
		fac = 2 * (N - j);
		mx = MAX;
		for (int k = MAX; k >= 0; k --) {
			nrmod[k + fac] = ((nrmod[k + fac] % MOD) + (nrmod[k] % MOD) % MOD);
			if (k + fac > mx) mx = k + fac;
		}

		MAX = mx;
	}

	printf("%d\n", nrmod[S]);
	
	return 0;
}