Cod sursa(job #1586182)

Utilizator rares98_priPopa Rares rares98_pri Data 31 ianuarie 2016 20:46:48
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define NMax 105
ifstream in ("lapte.in");
ofstream out ("lapte.out");
int n,l,rez=100;

struct pct{
    int A,B,id;
    bool operator<(const pct &t) const{
        if(A-B<t.A-t.B) return true;
        return false;}} a[NMax];

struct pct2{
    int A,B,id;
    bool operator<(const pct2 &t) const{
        if(id<t.id) return true;
        return false;}}s[NMax];

bool verif(int t){
int x=0,y=0,time;
for(int i=1;i<=n;i++){
    if(x<l){
        time=t/a[i].A;
        if(x+time<l){
            x+=time;
            s[i].A=time;
            s[i].B=0;}
        else{
            s[i].A=l-x;
            time=time-(l-x);
            time=time*a[i].A/a[i].B;
            x=l;
            y+=time;
            s[i].B=time;}}
    else{
        time=t/a[i].B;
        y+=time;
        s[i].B=time;
        s[i].B=0;}}
if(x>=l&&y>=l)return 1;
return 0;}

int main(){
in>>n>>l;
int i;
for(i=1;i<=n;i++){
        in>>a[i].A>>a[i].B;
        a[i].id=i;}
sort(a+1,a+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++)s[i].id=a[i].id;
    sort(s+1,s+n+1);
    out<<rez<<'\n';
for(i=1;i<=n;i++)out<<s[i].A<<" "<<s[i].B<<'\n';}