Cod sursa(job #7356)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 21 ianuarie 2007 13:30:40
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>

#define maxn 100
#define maxx 10000
#define mod 194767

int n,s,x,sol;
int c[maxn][maxx],d[maxn][maxx];

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