Cod sursa(job #8797)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 25 ianuarie 2007 16:55:13
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define maxn 32768
#define mod 194767

int n,s;
int c[maxn],d[maxn];

inline int min(int a,int b)
{
       if (a>b) return a;
       return b;
}

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