Cod sursa(job #790022)

Utilizator costyv87Vlad Costin costyv87 Data 20 septembrie 2012 01:00:15
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
FILE *f,*g;
int nr[20][20][20];
int sol[20][20];
int v[20];
int a[1000010][10];
int lim,i,mm,n,j,q,cl,s;

int main()
{
    f=fopen("triunghi.in","r");
    g=fopen("triunghi.out","w");

    fscanf(f,"%d%d",&n,&s);


    for (i=1;i<=n;i++)
        nr[1][i][i]=1;


    cl=n;

    for (i=2,mm=n-1;i<=n;i++,mm--)
        for (j=1;j<=mm;j++)
            for (q=1;q<=cl;q++)
                nr[i][j][q]=nr[i-1][j][q]+nr[i-1][j+1][q];


    for (mm=n,i=1;i<=n;i++,mm--)
        for (j=1;j<=mm;j++)
            for (q=1;q<=cl;q++)
                v[q]+=nr[i][j][q];

    if (n==1)
    {
        fprintf(g,"%d",s);
        fclose(g);
        return 0;
    }

    cl=n/2+n%2;

    if (s<2*v[1])
    {
        fprintf(g,"imposibil");
        fclose(g);
        return 0;
    }

    for (j=v[1];j<=s;j+=v[1])
        a[j][0]=1, a[j][1]=0;

    for (i=2;i<=cl;i++)
    {
        lim=s-v[i];
        for (j=1;j<=lim;j++)
            if (a[j][0]==i-1 && (j+v[i]*2<=s || (n%2==1 && j==cl) ) )
            {
                for (q=j+2*v[i];q<=s;q+=v[i])
                    a[q][0]=i, a[q][i]=j;
            }
    }


    for (i=s,j=cl;j>=1;j--)
    {
       if (a[s][0]==0)
       {
           fprintf(g,"imposibil");
           fclose(g);
           return 0;
       }

        sol[n][j]=(i-a[i][j])/v[j];

        i=a[i][j];
    }

    for (i=1;i<=n/2;i++)
    {
        if (sol[n][i]<=1)
        {
            fprintf(g,"imposibil");
            fclose(g);
            return 0;
        }
        sol[n][n+1-i]=1;
        sol[n][i]--;
    }
    if (n%2==1 && sol[n][cl]==0)
    {
        fprintf(g,"imposibil");
        fclose(g);
        return 0;
    }

    for (mm=n-1,i=n-1;i>=1;i--,mm--)
        for (j=1;j<=mm;j++)
            sol[i][j]=sol[i+1][j]+sol[i+1][j+1];

    for (mm=1,i=1;i<=n;i++,mm++,fprintf(g,"\n"))
        for (j=1;j<=mm;j++)
            fprintf(g,"%d ",sol[i][j]);

    fclose(g);
    return 0;
}