Pagini recente » Cod sursa (job #3246641) | Cod sursa (job #2660928) | Cod sursa (job #2887385) | Cod sursa (job #1133624) | Cod sursa (job #1059477)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,L,solT,solA[101],solB[101],t[101];;
struct om {int A, B; };
vector<om> v;
vector<int> ind;
bool cmp(int i, int j) {
return v[i].A-v[j].A<v[i].B-v[j].B;
}
int main() {
ifstream in("lapte.in");
ofstream out("lapte.out");
int i,l,r,mij,a,b,c,timp;
om o;
in>>n>>L;
for(i=0;i<n;i++) {
in>>o.A>>o.B;
v.push_back(o);
ind.push_back(i);
}
sort(ind.begin(), ind.end(), cmp);
l=1;r=100;
while(l<=r) {
mij=(l+r)/2;
a=b=L;
for(i=0;i<n;i++) {
timp=0; if(i>n-i-1) timp=t[i];
c=(mij-timp)/v[ind[i]].A;
if(c>a) c=a;
a-=c;
t[i]=c*v[ind[i]].A;
solA[ind[i]]=c;
timp=0; if(i>=n-i-1) timp=t[n-i-1];
c=(mij-timp)/v[ind[n-i-1]].B;
if(c>b) c=b;
b-=c;
t[n-i-1]=c*v[ind[n-i-1]].B;
solB[ind[i]]=c;
}
if(!a && !b) { r=mij-1; solT=mij; }
else l=mij+1;
}
out<<solT<<endl;
for(i=0;i<n;i++) out<<solA[i]<<" "<<solB[i]<<endl;
out.close();
return 0;
}