Cod sursa(job #1059477)

Utilizator mihai10stoicaFMI - Stoica Mihai mihai10stoica Data 16 decembrie 2013 18:50:48
Problema Lapte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#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;
}