Cod sursa(job #1059507)

Utilizator mihai10stoicaFMI - Stoica Mihai mihai10stoica Data 16 decembrie 2013 19:14:27
Problema Lapte Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
    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;
}