Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-08-25 16:20:04.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:viteze.in, viteze.outSursăJunior Challenge 2016
AutorCostin OncescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test0.175 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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). delta_i reprezinta diferenta maxima de viteze intre portiunea i - 1 si i (caz particular face delta_1 care este tot o limitare a primei viteze, dat fiind faptul ca pe portiunea imaginara 0, cocalarul are viteza de 0, lim_1 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 1 / v_1 + 1 / v_2 + ...1 / v_N .

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  lim_1 * lim_2 * ... * lim_{$N$} ≤ 500000
  • Subtask 2 (20 puncte): 1 ≤ N ≤ 100 si  lim_i ≤ 100
  • Subtask 3 (20 puncte): 1 ≤ N ≤ 1000 si  lim_i ≤ 1000
  • Subtask 4 (30 puncte): 1 ≤ N ≤ 100000 si  lim_i ≤ 109
  • Subtask 5 (20 puncte): 1 ≤ N ≤ 1000000 si  lim_i ≤ 109

Exemplu

viteze.inviteze.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?