Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | garaj.in, garaj.out | Sursă | preONI 2008, Runda 4 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Garaj
Intr-un garaj se afla N camioane, iar la usa garajului asteapta sa fie transportate la adapost M sticle cu suc natural de struguri. Fiecare camion i are o capacitate maxima Ci care reprezinta numarul maxim de sticle care pot fi la un moment dat in camion si un timp Ti minute in care parcurge distanta de la garaj la adapost (deci ca sa ajunga de la garaj la adapost si inapoi la garaj va circula 2*Ti minute). Proprietarul garajului, Samson, vrea sa transporte toate sticlele la adapost. El va alege anumite camioane pe care le va folosi la transport si fiecare camion dintre cele alese va face oricate drumuri garaj->adapost->garaj este nevoie pentru a transporta toate sticlele (camioanele trebuie sa se intoarca tot timpul la garaj pentru a finalizat cu succes transportul). El vrea sa minimizeze timpul maxim in care circula un camion, altfel spus vrea sa termine de transportat toate sticlele intr-un timp minim. Dupa ce a gasit acest timp minim, el vrea sa foloseasca si un numar minim de camioane din garaj pe care sa le foloseasca la tranport pentru a obtine acel timp minim.
Date de intrare
Fisierul de intrare garaj.in contine pe prima linie numerele naturale N si M, avand semnificatia din enunt. Pe urmatoarele N linii urmeaza cate o pereche de numere naturale C T reprezentand capacitatea maxima si timpul in care un camion efectueaza distanta garaj->adapost.
Date de iesire
In fisierul de iesire garaj.out se afla pe prima linie doua numere naturale Tmin si Nrmin, timpul minim in care se efectueaza transportul si numarul minim de camioane care trebuiesc folosite.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 109
- 1 ≤ C, T ≤ 1000
- Toate numerele din fisierul de intrare sunt numere naturale
Exemplu
| garaj.in | garaj.out |
|---|---|
| 3 16 5 3 6 2 4 1 | 6 2 |
Explicatie
O solutie posibila este urmatoarea: camionul 2 efectueaza un transport ducand 6 sticle la adapost iar camionul 3 realizeaza 3 transporturi, la primul si al doilea transporta cate 4 sticle iar la ultimul 2 sticle. Al doilea camion circula timp de 4 minute iar al treilea timp de 6 minute, deci dupa 6 minute toate sticlele au fost transportate. O alta solutie in care se obtine timpul minim 6 ar fi sa se foloseasca toate cele 3 camioane la tranport, dar nu ar mai fi folosite un numar minim de camioane.
