Cod sursa(job #239272)

Utilizator raduzerRadu Zernoveanu raduzer Data 4 ianuarie 2009 15:08:24
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <cstdio>
#include <cstdlib>

const int MAX_N = 33000;
const int MOD = 194767;

int n, s;
int d[2][MAX_N];

int main()
{
	int i, j, p;
	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);
	
	scanf("%d %d", &n, &s);
	
	if (s < 0) s = s * (-1);
	if (s > n * (n + 1) / 2) 
	{
        printf("0\n");
        return 0;        
    }
	
	d[1][0] = 1;
	for (i = 2, p = 0; i <= n; ++i, p = 1 - p)
		for (j = 0; j <= i * (i - 1) / 2; ++j)
			d[p][j] = (d[1 - p][abs(j - i + 1)] + d[1 - p][j + i - 1]) % MOD;
		
	printf("%d\n", d[1 - p][s]);
}