Cod sursa(job #20815)

Utilizator mariusdrgdragus marius mariusdrg Data 22 februarie 2007 12:44:24
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#include<algorithm>
#define mod %194767

using namespace std;

const int maxn = 10000;

int nr;
int n;
int m;
int a[maxn];
int pos[maxn];
int aux[maxn];
int pos1[maxn];

int j;
int i;
int s;


int modul(int m)
{
        if (m<0) return m*(-1);
        return m;
}

int main()
{
        freopen("1-sir.in","r",stdin);
        freopen("1-sir.out","w",stdout);
        scanf("%d %d",&n,&m);
        if ((modul(m)>(n*(n-1)/2))||(m%2!=(n*(n-1)/2)%2))
        {
                printf("0\n");
                return 0;
        }
        s=n*(n-1)/2-m;
        if (s==0)
        {
                printf("1\n");
                return 0;
        }
        for(i=1;i<=n-1;i++)
        {
                a[0]=1;
                pos1[0]=1;
                for(j=0;j<=s;j++)
                {
                        if (a[j]==1)
                        {
                                aux[j+2*i]=1;
                                pos[j+2*i]=(pos[j+2*i]+pos1[j])mod;
                        }
                }
                memcpy(a,aux,sizeof(aux));
                memcpy(pos1,pos,sizeof(pos));
                memset(aux,0,sizeof(aux));
                memset(pos,0,sizeof(pos));
                if (a[s]==1) nr=(nr+pos1[s])mod;

        }
        printf("%d\n",nr mod);
        return 0;
}