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 (vorba poetului - de la kilometrul 0 al fiţelor) 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 naturale de la 1 la N. Toate portiunile au lungimea 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). 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 \frac{1}{v_1} + \frac{1}{v_2} + ... + \frac{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 cu care K0Kalaru 47 va alege sa se deplaseze pe fiecare portiune in parte.

Restricţii

  •  1 \leq lim_i \leq 10^9 (pentru 1 ≤ i ≤ N)
  •  0 \leq delta_i \leq 10^9 (pentru 1 ≤ i ≤ N)
  • Se garanteaza ca exista solutie.
  • Cocalarul va sfatuieste sa ganditi problema ca si cum ati fi in locul lui.
  • Subtask 1 (10 puncte): 1 ≤ N ≤ 10 si  lim_1 \cdot lim_2 \cdot ... \cdot lim_{$N$} \leq 500.000 (Feedback testul 2)
  • Subtask 2 (20 puncte): 1 ≤ N ≤ 100 si  lim_i \leq 100  (Feedback testul 6)
  • Subtask 3 (20 puncte): 1 ≤ N ≤ 1.000 si  lim_i \leq 1.000 (Feedback testul 10)
  • Subtask 4 (30 puncte): 1 ≤ N ≤ 100.000 si  lim_i \leq 10^9  (Feedback testul 16)
  • Subtask 5 (20 puncte): 1 ≤ N ≤ 1.000.000 si  lim_i \leq 10^9 (Feedback testul 20)
  • 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.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 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?