Pagini recente » Cod sursa (job #3217289) | Cod sursa (job #2399278) | Cod sursa (job #1167747) | Cod sursa (job #1127014) | Cod sursa (job #1059506)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,L,solT,sA[101],sB[101],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;
string s,sol;
om o;
in>>n>>L;
for(i=0;i<n;i++) {
in>>o.A>>o.B;
v.push_back(o);
ind.push_back(i);
}
in.close();
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;
sA[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;
sB[ind[n-i-1]]=c;
}
if(!a && !b) {
r=mij-1; solT=mij;
for(i=0;i<n;i++) { solA[i]=sA[i]; solB[i]=sB[i]; }
}
else l=mij+1;
}
out<<solT<<endl;
for(i=0;i<n;i++) out<<solA[i]<<" "<<solB[i]<<endl;
out.close();
return 0;
}