Fişierul intrare/ieşire:lapte.in, lapte.outSursăpreONI 2004
AutorAdrian VladuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Lapte

Haralambie este un mare bautor de lapte. Impreuna cu prietenii sai organizeaza adesea petreceri salbatice, in care se intrec in bautul laptelui. De data aceasta ei au organizat un joc. Ei au doua feluri de lapte : lapte A si lapte B. In aceasta noapte si-au propus sa bea cel putin L litri din fiecare fel. Dar mai e putin si se face dimineata, parintii lui Haralambie se intorc acasa si petrecerea se sparge. Ajutati-i sa bea cat mai repede.

Cerinta

Se cunoaste viteza cu care fiecare persoana bea un litru din laptele A si laptele B. Trebuie planificata o strategie astfel incat la sfarsitul petrecerii sa fi baut cel putin L litri din laptele A si cel putin L litri din laptele B, iar timpul total sa fie minim. O persoana nu poate bea din doua tipuri de lapte in acelasi timp.

Date de intrare

Pe prima linie a fisierului de intrare lapte.in sunt scrise numerele N (numarul persoane participante) si L (cantitatea minima de lapte ce trebuie bauta pana la sfarsitul petrecerii). Pe urmatoarele N linii sunt date perechi de numere naturale nenule a b (1 ≤ a, b ≤ 100) reprezentand timpul in care persoana corespunzatoare bea 1 litru de lapte A, respectiv timpul in care bea 1 litru de lapte B.

Date de iesire

Prima linie a fisierului lapte.out va contine un singur numar T - timpul minim in care se va bea cantitatea ceruta de lapte. Pe urmatoarele N linii vor fi perechi de numere naturale. Linia i + 1 va contine numerele x y , reprezentand cantitatea de lapte A, respectiv cantitatea de lapte B pe care o bea persoana i.

Restrictii si precizari

  • 1 ≤ N, T, L ≤ 100
  • Cantitatea de lapte disponibila se considera nelimitata
  • Consumul excesiv de lapte duce la epuizarea bauturii

Exemplu

lapte.inlapte.out
3 20
1 1
2 4
1 6
18
0 18
5 2
18 0

Explicatii

Timpul minim este 18.
Cantitatea de lapte A bauta este 0+5+18=23.
Cantitatea de lapte B bauta este 18+2=20.
Persoana 1 termina de baut in 1*0+1*18=18 minute.
Persoana 2 termina in 2*5+4*2=18 minute.
Persoana 3 termina in 1*18+6*0=18 minute.
Timpul minim dupa care petrecerea va lua sfarsit este max(18,18,18)=18

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content