Cod sursa(job #524295)

Utilizator siminescuPaval Cristi Onisim siminescu Data 20 ianuarie 2011 21:47:16
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#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';
}