Cod sursa(job #1072913)

Utilizator RamaStanciu Mara Rama Data 5 ianuarie 2014 12:36:18
Problema Lapte Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("lapte.in");
ofstream out ("lapte.out");

int n, L, combo=-5;

struct drinker
{
    int L1, L2, pos;
};

drinker P[100];

int compair(const drinker &d1,const drinker &d2)
{
    int val=d1.L1 - d1.L2;
    int val2=d2.L1 - d2.L2;
    if (val<val2) return val;
        else return val2;

}

int compair2(const drinker &d1,const drinker &d2)
{
    if (d1.pos<d2.pos) return d1.pos;
        else return d2.pos;

}

int compair3(int a, int b)
{
    if (a<b) return a;
        else return b;
}

void print()
{
    for (int i=1;i<=n;i++)
        out<<P[i].L1<<" "<<P[i].L2<<"\n";
}

int main()
{
    in>>n>>L;
    for (int i=1;i<=n;i++)
    {
        in>>P[i].L1>>P[i].L2;
        P[i].pos=i;
    }

    sort(P+1,P+n+1,compair);

    int st=1,dr=L*100*100;
    while (st<=dr)
    {
        int mid=(st+dr)/2,LA=L,LB=L,time[100];
        for (int i=1;i<=n;i++)
        {
            int drunk=compair3(LA,mid/P[i].L1);
            LA=LA-drunk;
            time[i]=drunk*P[i].L1;
        }

        for (int i=n;i>0 && LB>0;i--)
            LB=LB-(mid-time[i])/P[i].L2;

        if (LA<1 && LB<1)
           {
             combo=mid;
             dr=mid-1;
           }
        else
            st=mid+1;
    }
    out<<combo<<"\n";

    int LA=L,LB=L,time[100];
    for (int i=1;i<=n;i++)
        {
            int drunk=compair3(LA,combo/P[i].L1);
            LA-=drunk;
            time[i]=drunk*P[i].L1;
            P[i].L1=drunk;

        }
    for (int i=n;i>0;i--)
        {
            int drunk=compair3(LB,(combo-time[i])/P[i].L2);
            LB-=drunk;
            P[i].L2=drunk;
            //cout<<"*"<<P[i].L2<<"\n";
        }

    sort(P+1,P+n+1,compair2);

    print();

    return 0;
}