Pagini recente » Cod sursa (job #2362145) | Borderou de evaluare (job #2371482) | Cod sursa (job #2369247)
#include <fstream>
using namespace std;
ifstream fin("lapte.in");
ofstream fout("lapte.out");
int n,L,st,dr,mid,a[110],b[110],D[110][110],T[110][110],i;
int ok(int t){
int i,j,k,verif=0;
for(i=1;i<=n;i++)
for(j=0;j<=L;j++)
D[i][j]=-1;
for(j=0;j<=min(L,t/a[1]);j++){
D[1][j]=(t-a[1]*j)/b[1];
T[1][j]=j;
}
for(i=2;i<=n;i++)
for(j=0;j<=min(L,t/a[i]);j++)
for(k=0;k<=L-j;k++)
if(D[i-1][k]!=-1&&D[i-1][k]+(t-a[i]*j)/b[i]>D[i][j+k]){
D[i][j+k]=D[i-1][k]+(t-a[i]*j)/b[i];
T[i][j+k]=j;
if(k+j==L&&D[i][j+k]>=L)
verif=1;
}
return verif;
}
void drum(int n, int L){
if(n>0){
drum(n-1,L-T[n][L]);
fout<<T[n][L]<<" "<<(st-T[n][L]*a[n])/b[n]<<"\n";
}
}
int main (){
fin>>n>>L;
for(i=1;i<=n;i++)
fin>>a[i]>>b[i];
st=1;
dr=10000;
while(st<=dr){
mid=(st+dr)/2;
if(ok(mid))
dr=mid-1;
else
st=mid+1;
}
fout<<st<<"\n";
drum(n,L);
return 0;
}