Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tractor2.in, tractor2.out | Sursă | Grigore Moisil 2018, 10 |
| Autor | Alex Cociorva, Mircea Popoveniuc, Razvan Salajan | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tractor2
În oraşul Târgu Mureş, există un parc de distracţii mai puţin cunoscut. Atracţia principală este XTreme Tractor - un tractor de mare viteză, singurul care a mai rămas din seria sa de tractoare de mare viteză. Personalul parcului doreşte să gestioneze cât mai bine vizitatorii care se urcă în el.
Înainte de îmbarcare, lumea se aşază la una dintre cele două cozi de la intrare: prima coadă este destinată doar persoanelor venite singure, iar a doua coadă este destinată doar persoanelor venite în grupuri de câte 2, 3 sau 4. Persoanele dintr-un grup nu se pot separa şi se vor da cu tractorul împreună. Persoanele din prima coadă şi grupurile din a doua coadă se aşază în coada corespunzătoare la diverse momente de timp, dar, în cadrul aceleiaşi cozi, vor exista doar timpi de intrare distincţi. Pe parcursul zilei, vor intra N persoane în prima coadă şi M grupuri în a doua coadă. În plus, pe lângă timpul de intrare în coada corespunzătoare, se mai cunoaşte, pentru fiecare persoană şi pentru fiecare grup, durata de îmbarcare.
Din motive economice, conducerea parcului doreşte ca la fiecare cursă cu tractorul să se urce exact 4 vizitatori. O persoană sau un grup dintr-o coadă poate urca în tractor doar dacă au urcat toate persoanele sau grupurile din faţă din coada respectivă. Se pot cupla să urce împreună persoane sau grupuri din aceeaşi coadă, dar şi din cozi diferite. După ce s-au ales cei 4 vizitatori pentru cursa curentă, durata de îmbarcare pentru cursa curentă va fi maximul duratelor de îmbarcare pentru vizitatorii aleşi (adică persoanele şi grupurile). De asemenea, durata unei curse cu tractorul este de P secunde. Datorită faptului că există un singur tractor, următorii 4 vizitatori care vor să se urce trebuie să aştepte să se termine cursa curentă.
De exemplu, să considerăm că pentru cursa curentă au fost aleşi: o persoană ajunsă la momentul 15 cu durata de îmbarcare 6, o persoană ajunsă la momentul 18 cu durata de îmbarcare 4 şi un grup de 2 persoane ajuns la momentul 20 cu durata de îmbarcare 5. Durata cursei este 10. Dacă tractorul este liber la momentul 20, atunci cele 4 persoane se vor îmbarca cu durata max(6,4,5)=6, adică la momentul 26, iar cursa va avea durata 10, adică se va termina la momentul 36.
Ajutaţi conducerea să afle timpul minim în care toate persoanele şi grupurile din ambele cozi se dau cu tractorul.
Date de intrare
Fişierul de intrare tractor.in conţine pe prima linie numerele întregi N, M şi P, cu semnificaţia: N - numărul de persoane ce intră în prima coadă; M - numărul de grupuri ce intră în a doua coadă; P - durata unei curse cu tractorul.
Pe următoarele N+M linii, se află câte trei numere întregi t d c. Dacă d este 1, atunci este vorba de o persoană care la momentul t se aşază în prima coadă şi are durata de îmbarcare c. Dacă d este 2, 3 sau 4, atunci este vorba de un grup de d persoane care la momentul t se aşază în a doua coadă şi are durata de îmbarcare c. Timpii daţi în fişierul de intrare sunt în ordine crescătoare.
Date de ieşire
Fişierul de ieşire tractor.out trebuie să conţină un singur număr întreg T care reprezintă timpul minim în care toate persoanele din prima coadă şi grupurile din a doua coadă se dau cu tractorul.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| tractor2.in | tractor2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
