Cod sursa(job #1575872)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 21 ianuarie 2016 21:52:44
Problema Lapte Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct om
{
    int v1,v2,id;
};

struct sol
{
    int v1,v2,id;
};

bool myfunction (om i,om j)
{
    if(i.v1==j.v1) return i.v2>j.v2;
    return i.v1< j.v1;
}

bool mycomp ( sol i,sol j)
{
    return i.id<j.id;
}

om pers[101];
sol sol[101];

int n,l;

/*int isok(int tmp)
{
    int j,i,c1=0,c2=0,ca1=0,ca2=0;
    for(i=1;i<=n;i++)
    {
        sol[i].id=pers[i].id; sol[i].v1=0; sol[i].v2=0;

        if(c1>=l) { ca2=tmp/pers[i].v2; c2+=ca2; sol[i].v2=ca2; }
        else
        {
            if(l-c1 > tmp/pers[i].v1) { ca1=tmp/pers[i].v1; c1+=ca1; sol[i].v1=ca1; }
            else
            {
                sol[i].v1=l-c1;
                ca2=(tmp-(l-c1))*pers[i].v1/pers[i].v2;
                c1=l;
                c2+=ca2; sol[i].v2=ca2;
            }
        }
    }

    if(c1>=l && c2>=l) return 1;
    else return 0;
}*/

bool isok(int T)
{
    int A = 0, B = 0, time;

    for(int i=1;i<=n;++i)
    {
        if(A < l)
        {
            time = T / pers[i].v1;

            if(A + time < l)
            {
                A += time;
                sol[i].v1 = time;
                sol[i].v2 = 0;
            }
            else
            {
                sol[i].v1 = l-A;

                time = time - (l-A);
                time = time * pers[i].v1 / pers[i].v2;
                A = l;
                B += time;

                sol[i].v2 = time;
            }
        }
        else
        {
            time = T / pers[i].v2;
            B += time;
            sol[i].v2 = time;
            sol[i].v1 = 0;
        }
    }

    if(A >= l && B >= l) return true;
    return false;
}

int rez=100;

int main()
{
    freopen("lapte.in","r",stdin);
    freopen("lapte.out","w",stdout);
    int poz,i;
    cin>>n>>l;
    for(i=1;i<=n;i++) { cin>>pers[i].v1>>pers[i].v2; pers[i].id=i; }
    sort(pers+1,pers+n+1,myfunction);

    int st,dr,mij;
    st = 1, dr = 100;
    while(st <= dr)
    {
        mij = (st+dr)/2;
        if(isok(mij))
        {
            if(mij < rez) rez = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    cout<<rez<<'\n';
    for(i=1;i<=n;++i) sol[i].id = pers[i].id;
    isok(rez);
    sort(sol+1,sol+n+1,mycomp);
    for(i=1;i<=n;i++) cout<<sol[i].v1<<' '<<sol[i].v2<<'\n';
    return 0;
}