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 aceasta diferenta maxima de viteze intre portiunea &i - 1& si &i& (caz particulare 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).
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 pe cu cate va alege K0Kalaru 47 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
- Subtask 2 (20 puncte): 1 ≤ N ≤ 100 si ≤ 100
- Subtask 3 (20 puncte): 1 ≤ N ≤ 1000 si ≤ 1000
- Subtask 4 (30 puncte): 1 ≤ N ≤ 100000 si ≤ 109
- Subtask 5 (20 puncte): 1 ≤ N ≤ 1000000 si ≤ 109
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