Cod sursa(job #838159)

Utilizator elfusFlorin Chirica elfus Data 19 decembrie 2012 00:33:43
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#define MOD 194767

inline void baga(int &A, int B)
{
	A += B;
	if (A >= MOD)
		A = A - MOD;
}

inline int ab(int X)
{
	if (X > 0)
		return X;
	return X * (-1);
}

int dp[2][90000];

int main()
{
	int i, j, N, S;
	
	freopen("1-sir.in", "r", stdin);
	freopen("1-sir.out", "w", stdout);
	
	scanf("%d%d", &N, &S);
	S = ab(S);
	if (N * (N + 1) / 2 < S)
	{
		printf("0");
		return 0;
	}
	
	int sol = 0;
	
	dp[1][0] = 1;
	for (i = 1; i <= N; i ++)
		for (j = 0; j <= S; j ++)
		{
			if (j + i <= S)
				baga(dp[(i + 1) & 1][j + i], dp[i & 1][j]);
			if (ab(j - i) <= S)
				baga(dp[(i + 1) & 1][ab(j - i)], dp[i & 1][j]);
			if (i == N && j == S)
				sol = dp[i & 1][j];
			dp[i & 1][j] = 0;
		}
		
	printf("%d", sol / 2);
	return 0;
}