Pagini recente » Cod sursa (job #1224891) | Cod sursa (job #2222401) | Cod sursa (job #2887078) | Cod sursa (job #1190980) | Cod sursa (job #1575872)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct om
{
int v1,v2,id;
};
struct sol
{
int v1,v2,id;
};
bool myfunction (om i,om j)
{
if(i.v1==j.v1) return i.v2>j.v2;
return i.v1< j.v1;
}
bool mycomp ( sol i,sol j)
{
return i.id<j.id;
}
om pers[101];
sol sol[101];
int n,l;
/*int isok(int tmp)
{
int j,i,c1=0,c2=0,ca1=0,ca2=0;
for(i=1;i<=n;i++)
{
sol[i].id=pers[i].id; sol[i].v1=0; sol[i].v2=0;
if(c1>=l) { ca2=tmp/pers[i].v2; c2+=ca2; sol[i].v2=ca2; }
else
{
if(l-c1 > tmp/pers[i].v1) { ca1=tmp/pers[i].v1; c1+=ca1; sol[i].v1=ca1; }
else
{
sol[i].v1=l-c1;
ca2=(tmp-(l-c1))*pers[i].v1/pers[i].v2;
c1=l;
c2+=ca2; sol[i].v2=ca2;
}
}
}
if(c1>=l && c2>=l) return 1;
else return 0;
}*/
bool isok(int T)
{
int A = 0, B = 0, time;
for(int i=1;i<=n;++i)
{
if(A < l)
{
time = T / pers[i].v1;
if(A + time < l)
{
A += time;
sol[i].v1 = time;
sol[i].v2 = 0;
}
else
{
sol[i].v1 = l-A;
time = time - (l-A);
time = time * pers[i].v1 / pers[i].v2;
A = l;
B += time;
sol[i].v2 = time;
}
}
else
{
time = T / pers[i].v2;
B += time;
sol[i].v2 = time;
sol[i].v1 = 0;
}
}
if(A >= l && B >= l) return true;
return false;
}
int rez=100;
int main()
{
freopen("lapte.in","r",stdin);
freopen("lapte.out","w",stdout);
int poz,i;
cin>>n>>l;
for(i=1;i<=n;i++) { cin>>pers[i].v1>>pers[i].v2; pers[i].id=i; }
sort(pers+1,pers+n+1,myfunction);
int st,dr,mij;
st = 1, dr = 100;
while(st <= dr)
{
mij = (st+dr)/2;
if(isok(mij))
{
if(mij < rez) rez = mij;
dr = mij - 1;
}
else st = mij + 1;
}
cout<<rez<<'\n';
for(i=1;i<=n;++i) sol[i].id = pers[i].id;
isok(rez);
sort(sol+1,sol+n+1,mycomp);
for(i=1;i<=n;i++) cout<<sol[i].v1<<' '<<sol[i].v2<<'\n';
return 0;
}