Cod sursa(job #20825)

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

using namespace std;

const int maxn = 50000;

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)
                        {
                                if (j+2*i>s) break;
                                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));
                if (a[s]==1)
                {
                        nr=(nr+pos1[s])mod;
                        pos1[s]=0;
                        pos[s]=0;
                }

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