Cod sursa(job #42065)

Utilizator gigi_becaliGigi Becali gigi_becali Data 28 martie 2007 20:25:50
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#define maxn 100
#define mod 194767

int dp[maxn][maxn*(maxn-1)];
int N, S;
const int maxt=maxn*(maxn-1)>>1;
int sgn(int a)
{
	if(a<0) return -a;
	return a;
}

int main()
{
	freopen("1-sir.in", "r", stdin);
	scanf("%d %d\n", &N, &S);
	int i, j;
	dp[1][1]=1;
	
	for(i=2;i<=N;i++)
		for(j=-S;j<=S;j++)
		{
			dp[i][j]=dp[i-1][j+(i-1)];
			dp[i][j]+=dp[i-1][sgn(j-(i-1))];
			
			//dp[i][j]=dp[i-1][j-(i)]+dp[i-1][j+(i)], dp[i][j]%=mod;
			dp[i][j+maxt]%=mod;
		}
	

	for(i=1;i<=N;i++) 
	{
		for(j=0;j<=S;j++) printf("%d ", dp[i][j]);
		printf("\n");
	}
	
	freopen("1-sir.out", "w", stdout);
	printf("%d\n", dp[N-1][sgn(S)]);
	return 0;
}