Pagini recente » Cod sursa (job #346676) | Cod sursa (job #48919) | Cod sursa (job #2787376) | Cod sursa (job #2221078) | Cod sursa (job #524295)
Cod sursa(job #524295)
#include<fstream>
using namespace std;
ifstream f("lapte.in");
ofstream g("lapte.out");
# define nmax 102
typedef struct tip{
int A,B,la,lb,t,nr; long double ef;
}; tip v[nmax];
int N,L,LA,LB;
void citire()
{
f>>N>>L;
int i;
for(i=1;i<=N;i++)
{
f>>v[i].A>>v[i].B;
v[i].ef=(long double)v[i].A/v[i].B;
v[i].nr=i;
}
}
int cmp1(tip i,tip j)
{
if(i.ef==j.ef) return i.A<j.A;
return i.ef<j.ef;
}
int verific(int T)
{
LA=LB=L; int i;
for(i=1;i<=N;++i)
{
if(LA*v[i].A<=T)
{
v[i].la=LA; v[i].t=LA*v[i].A;
LA=0;
}
else
{
v[i].la=T/v[i].A; v[i].t=v[i].A*v[i].la;
LA-=v[i].la;
}
}
if(LA) return 0;
for(i=N;i;--i)
{
if(LB*v[i].B<=T-v[i].t)
{
v[i].lb=LB; //v[i].t+=LB*v[i].B;
LB=0;
}
else
{
v[i].lb=(T-v[i].t)/v[i].B; //v[i].t+=v[i].B*v[i].lb;
LB-=v[i].lb;
}
}
if(LB) return 0;
return 1;
}
int BS(int st,int dr)
{
if(st==dr) return st;
int mij=(st+dr)/2+1;
if(verific(mij))
return BS(st,mij-1);
else return BS(mij,dr);
}
int cmp2(tip i,tip j)
{
return i.nr<j.nr;
}
int main()
{
citire();
int i,T;
sort(v+1,v+1+N,cmp1);
T=BS(1,150); g<<T<<'\n';
verific(T); sort(v+1,v+N+1,cmp2);
for(i=1;i<=N;i++) g<<v[i].la<<' '<<v[i].lb<<'\n';
}