Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | viteze.in, viteze.out | Sursă | Junior Challenge 2016 |
Autor | Costin Oncescu | Adăugată de | JuniorChallenge2016 •JuniorChallenge2015 |
Timp execuţie pe test | 0.175 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Viteze
K0Kalaru 47 a reusit anul trecut sa ia locul 2 la JBOI (foarte aproape sa ia maxim) obtinand astfel bani si faima. Ca orice cocalar care se respecta, acesta si-a cumparat un BMW pentru a nu mai fi nevoit sa imprumute calul vecinului. Din pacate, acesta inca sta destul de prost cu actele si de aceea nu vrea sa fie tras pe dreapta de catre politia rutiera (amenda nu este o problema, data fiind averea sa inestimabila).
Anul acesta, pentru a ajunge la JBOI, cocalarul va folosi o autostrada care porneste fix din curtea casei sale si se termina la hotelul unde va avea loc balcaniada. Autostrada este impartita in N portiuni, fiecare cu propria ei limita de viteza, portiunile fiind numerotate cu numere de la 1 la N. Toate portiunile au lungime de o unitate, iar vitezele si limtele acestora sunt exprimate in unitati pe secunda.
De asemenea, conditiile meteorolgice impun si ele anumite restrictii: la trecerea de pe o portiune pe alta exista o limita de acceleratie/franare pe care K0Kalaru 47 trebuie sa o respecte pentru a nu derapa (aceasta limita reprezinta practic diferenta maxima dintre vitezele cocalarului pe portiuni consecutive ale autostrazii). reprezinta diferenta maxima de viteze intre portiunea i - 1 si i (caz particular face care este tot o limitare a primei viteze, dat fiind faptul ca pe portiunea imaginara 0, cocalarul are viteza de 0, reprezentand acceleratia maxima la momentul plecarii). Pentru simplitate in cadrul unei portiuni, cocalarul isi va mentine viteza constanta.
Ca de obicei, voi trebuie sa-l ajutati pe cocalar, calculandu-i vitezele optime astfel incat sa ajunga cat mai devreme la JBOI. Timpul total este calculat ca fiind .
Date de intrare
Fişierul de intrare viteze.in va contine pe prima linie un singur numar natural N (numarul de portiuni ale autostrazii), pe a doua linie N numere naturale nenule separate prin spatii, semnificand limitele de viteze pe fiecare dintre portiuni si pe a treia linie inca N numere naturale, de data aceasta posibil nule, separate prin spatii care reprezinta vectorul delta.
Date de ieşire
În fişierul de ieşire viteze.out se vor afise pe prima si singura linie N numere naturale nenule reprezentand vitezele cu care K0Kalaru 47 va alege sa se deplaseze pe fiecare portiune in parte.
Restricţii
- Atentie! Fiecare subtask are testele grupate!
- Subtask 1 (10 puncte): 1 ≤ N ≤ 10 si ≤ 500000 (Feedback testul 2)
- Subtask 2 (20 puncte): 1 ≤ N ≤ 100 si ≤ 100 (Feedback testul 6)
- Subtask 3 (20 puncte): 1 ≤ N ≤ 1000 si ≤ 1000 (Feedback testul 10)
- Subtask 4 (30 puncte): 1 ≤ N ≤ 100000 si ≤ 109 (Feedback testul 16)
- Subtask 5 (20 puncte): 1 ≤ N ≤ 1000000 si ≤ 109 (Feedback testul 20)
- Cocalarul va sfatuieste sa ganditi problema ca si cum ati fi in locul lui.
- ATENŢIE! Se recomandă parsarea fişierelor viteze.in şi viteze.out pentru obţinerea scorului maxim. Puteţi folosi codul oferit de noi pe siteurile in şi out (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)
Exemplu
viteze.in | viteze.out |
---|---|
4 3 4 1 3 5 3 2 1 | 3 3 1 2 |
Explicaţie
Sirul optim de viteze este unic determinat in exemplu, reprezentand pentru K0Kalaru 47 o strategie prin care va ajunge la JBOI in 1/3 + 1/3 + 1/1 + 1/2 = 2.1(6) secunde. Acesta nu va derapa deoarece |0 - 3| ≤ 5, |3 - 3| ≤ 3, |3 - 1| ≤ 2 si |1 - 2| ≤ 1. De asemenea, cocalarul nu va fi depasi limita de viteza la niciun moment deoarece 3 ≤ 3, 3 ≤ 4, 1 ≤ 1 si 2 ≤ 3