Cod sursa(job #1416701)

Utilizator vazanIonescu Victor Razvan vazan Data 8 aprilie 2015 19:31:46
Problema Energii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include<cstdio>
#include<cstring>
using namespace std;

struct TRIPLE
{
    int prev, adag, deadag;
};


int v[19], ans[19][19];
TRIPLE d[1000000];

inline void genv(int n)
{
    register int i, j, k;
    int tr[19][19];
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
                tr[j][k]=0;
        tr[1][i]=1;
        v[i]=1;
        for(j=2; j<=n; j++)
            for(k=1; k<=n-j+1; k++)
            {
                tr[j][k]=tr[j-1][k+1]+tr[j-1][k];
                v[i]+=tr[j][k];
            }
    }
}

inline void recon(int n, int s)
{
    register int i, j;
    for(i=1; i<=n; i++)
        ans[1][i]=1;
    i=s;
    while(d[i].prev!=-1)
    {
        ans[1][d[i].adag]+=d[i].deadag;
        i=d[i].prev;
    }
    for(i=2; i<=n; i++)
        for(j=1; j<=n-i+1; j++)
            ans[i][j]=ans[i-1][j]+ans[i-1][j+1];
}

int main()
{
    FILE *in, *out;
    in=fopen("triunghi.in", "r");
    out=fopen("triunghi.out", "w");
    register int n, s, i, sum, smax;
    fscanf(in, "%d%d", &n, &s);
    smax=0;
    sum=0;
    genv(n);
    for(i=1; i<=n; i++)
        sum+=v[i];
    if(sum>s)
    {
        fprintf(out, "imposibil");
        return 0;
    }
    register int mul, j;
    smax=sum;
    d[smax].prev=-1;
    d[smax].adag=0;
    d[smax].deadag=0;
    for(i=1; i<=n/2+n%2&&(!d[s].prev); i++)
    {
        for(j=smax; j>=sum&&(!d[s].prev); j--)
        {
            if(d[j].prev)
            {
                mul=1;
                while(j+v[i]*mul<=s)
                {
                    if(!d[j+v[i]*mul].prev)
                    {
                        d[j+v[i]*mul].prev=j;
                        d[j+v[i]*mul].adag=i;
                        d[j+v[i]*mul].deadag=mul;
                        if(j+v[i]*mul>smax)
                            smax=j+v[i]*mul;
                    }
                    mul++;
                }
            }
        }
    }
    if(!d[s].prev)
    {
        fprintf(out, "imposibil");
    }
    else
    {
        recon(n, s);
        for(i=n; i>=1; i--)
        {
            for(j=1; j<=n-i+1; j++)
                fprintf(out, "%d ", ans[i][j]);
            fprintf(out, "\n");
        }
    }
    return 0;
}