Cod sursa(job #7008)

Utilizator wefgefAndrei Grigorean wefgef Data 21 ianuarie 2007 11:44:06
Problema 1-sir Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 0.71 kb
#include <cstdio>

#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define mod 194767

int n, s;
int v[70000];

void readdata()
{
	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);
	
	scanf("%d %d", &n, &s);
}

void solve()
{
	int i, j, lim;
	
	s = (n*(n-1)/2-s);
		
	if (s%2 == 1)
	{
		printf("0\n");
		return;
	}
	
	s/=2;
	if (s < 0 || s >= 70000)
	{
		printf("0\n");
		return;
	}
	
	v[0] = 1;
	lim = 0;
	for (i = 1; i < n; ++i)
	for (j = min(lim, s-i); j >= 0; --j)
	if (v[j])
	{
		lim = max(lim, j+i);
		v[j+i] += v[j];
		if (v[j+i] >= mod) v[j+i] -= mod;
	}
	printf("%d\n", v[s]);
}

int main()
{
	readdata();
	solve();
	return 0;
}