Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <algorithm>
- using namespace std;
- #define NMax 105
- ifstream f("lapte.in");
- ofstream g("lapte.out");
- int n,L;
- struct pct
- {
- int A,B,id;
- bool operator < (const pct &t) const
- {
- if(A-B < t.A-t.B) return true;
- return false;
- }
- } v[NMax];
- struct pct2
- {
- int A,B,id;
- bool operator < (const pct2 &t) const
- {
- if(id < t.id) return true;
- return false;
- }
- } sol[NMax];
- bool verif(int T)
- {
- int A = 0, B = 0, time;
- for(int i=1;i<=n;++i)
- {
- if(A < L)
- {
- time = T / v[i].A;
- if(A + time < L)
- {
- A += time;
- sol[i].A = time;
- sol[i].B = 0;
- }
- else
- {
- sol[i].A = L-A;
- time = time - (L-A);
- time = time * v[i].A / v[i].B;
- A = L;
- B += time;
- sol[i].B = time;
- }
- }
- else
- {
- time = T / v[i].B;
- B += time;
- sol[i].B = time;
- sol[i].A = 0;
- }
- }
- if(A >= L && B >= L) return true;
- return false;
- }
- int rez = 100;
- int main()
- {
- int i;
- f>>n>>L;
- for(i=1;i<=n;++i)
- {
- f>>v[i].A>>v[i].B;
- v[i].id = i;
- }
- sort(v+1,v+n+1);
- int st,dr,mij;
- st = 1, dr = 100;
- while(st <= dr)
- {
- mij = (st+dr)/2;
- if(verif(mij))
- {
- if(mij < rez) rez = mij;
- dr = mij - 1;
- }
- else
- {
- st = mij + 1;
- }
- }
- verif(rez);
- for(i=1;i<=n;++i) sol[i].id = v[i].id;
- sort(sol+1,sol+n+1);
- g<<rez<<"\n";
- for(i=1;i<=n;++i) g<<sol[i].A<<" "<<sol[i].B<<"\n";
- f.close();
- g.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement