Cod sursa(job #1015244)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 24 octombrie 2013 09:57:40
Problema Lapte Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <cstdio>
using namespace std;
int n,l,t,i,j,k,a[131],b[131],d[131][131],c[131][131];
void afis(int x, int y, int z)
{
    if(x!=0)
    {
        afis(x-1,y-c[x][y],y);
        printf("%d %d\n",c[x][y],(t-c[x][y]*a[x])/b[x]);
    }
}
int main()
{
    freopen("lapte.in","r",stdin);
    freopen("lapte.out","w",stdout);
    scanf("%d%d",&n,&l);
    for(i=1;i<=n;++i)
        scanf("%d%d",&a[i],&b[i]);
    for(t=1;t<=100;++t)
    {
        for(i=0;i<=n;++i)
            for(j=0;j<=l;++j)
                d[i][j]=-101;
        d[0][0]=0;
        for(i=1;i<=n;++i)
            for(k=0;k<=l;++k)
                for(j=0;j*a[i]<=t;++j)
                    if(d[i][k]<d[i-1][k-j]+(t-j*a[i])/b[i])
                    {
                        c[i][k]=j;
                        d[i][k]=d[i-1][k-j]+(t-j*a[i])/b[i];
                    }
        if(d[n][l]>=l)
        {
            printf("%d\n",t);
            afis(n,l,t);
            return 0;
        }
    }
    return 0;
}