Cod sursa(job #119679)

Utilizator sealTudose Vlad seal Data 2 ianuarie 2008 17:03:51
Problema Lapte Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>
#define Nm 101
int C[Nm][Nm],A[Nm],B[Nm],n,l;

void read()
{
    int i;

    freopen("lapte.in","r",stdin);
    scanf("%d%d",&n,&l);
    for(i=0;i<n;++i)
        scanf("%d%d",A+i,B+i);
}

int ok(int t)
{
    int M[2][Nm],i,j,k,c,p,m;

    M[0][0]=0;
    for(i=1;i<=l;++i)
        M[0][i]=-1;
    
    for(c=1,p=0,i=n-1;i>=0;--i,c^=1,p^=1)
    {
        for(j=0;j<=l;++j)
            M[c][j]=-1;
        for(j=0;j<=l;++j)
        {
            if(M[p][j]==-1)
                continue;
            for(k=0;j+k<=l && k*A[i]<=t;++k)
            {
                m=M[p][j]+(t-k*A[i])/B[i];
                if(m>M[c][j+k])
                {
                    M[c][j+k]=m;
                    C[j+k][i]=k;
                }
            }
        }
    }
    return M[p][l]>=l;
}

int solve()
{
    int l,r,m;

    l=1; r=100;
    while(l<r)
    {
        m=l+r>>1;
        if(ok(m))
            r=m;
        else
            l=m+1;
    }
    ok(l);
    return l;
}

void write(int t)
{
    int i;

    freopen("lapte.out","w",stdout);
    printf("%d\n",t);
    for(i=0;i<n;++i)
    {
        printf("%d %d\n",C[l][i],(t-C[l][i]*A[i])/B[i]);
        l-=C[l][i];
    }
}
    
int main()
{
    read();
    write(solve());
    return 0;
}