Cod sursa(job #282526)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 17 martie 2009 20:36:50
Problema Diamant Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#include<stdlib.h>
#define MOD 10000
int n;
int i;
int vs;
int nr[100003];
int no[100003];
int j;
int max;
int k;
int mij;
int m;
long long x;

int main()
{
        freopen("diamant.in","r",stdin);
        freopen("diamant.out","w",stdout);

        scanf("%d %d %lld",&n, &m, &x);
        mij = 50000;
        for(i = 1; i <= n; i++)
         for(j = 1; j <= m; j++)
             max += i * j;
        if (abs(x) > max)
             {
             printf("0\n");
             return 0;
             }

        no[mij] = 1;
        nr[mij] = 1;
        for(i = 1; i <= n; i++)
         for(j = 1; j <= m; j++)
            {
                    int val = i * j;
                    for(k = 100000; k >=0; k--)
                        if (no[k])
                         {
                         no[k+val] = 1;
                         nr[k+val] = (nr[k+val] + nr[k]) % MOD;
                         }
                    no[mij + val] = 1;
                    nr[mij + val] += 1;
                    no[mij - val] = 1;
                    nr[mij - val] += 1;

            }
        printf("%d", nr[mij+x]);
        return 0;
}