Cod sursa(job #485417)

Utilizator DraStiKDragos Oprica DraStiK Data 18 septembrie 2010 12:14:00
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <algorithm>
using namespace std;

#define DIM 100

long long bst[2][DIM],nr[DIM][DIM];
long long comb[DIM];
int n,m,k;

inline long long calc (long long x,int y)
{
    long long sol;
    int i;

    sol=1;
    for (i=1; i<=y; ++i)
        sol=(sol*(x-y+i))/i;
    return sol;
}

void read_solve ()
{
    int i,j,l,p;

    scanf ("%d%d%d",&n,&m,&k);
    bst[0][1]=bst[1][1]=nr[1][0]=1;
    for (p=1; p<n; ++p)
    {
        for (i=1; i<=n; ++i)
            comb[i]=calc (bst[1][p]+i-1,i);
        for (i=n; i>=p+1; --i)
            for (j=1; j<i; ++j)
                for (l=1; l<=j && l*p<i; ++l)
                    nr[i][j]+=nr[i-l*p][j-l]*comb[l];
        for (i=1; i<=p; ++i)
            if (i%m==k)
                bst[0][p+1]+=nr[p+1][i];
        for (i=1; i<=p; ++i)
            if (i%m==(m+k-1)%m)
                bst[1][p+1]+=nr[p+1][i];
    }
    printf ("%lld",bst[0][n]);
}

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

    read_solve ();

    return 0;
}