Fişierul intrare/ieşire:colete.in, colete.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Colete

Pe pasunea minunilor se afla N copii, copilul i avand casa la punctul de coordonate (x_i,y_i)(in metri). Fiecare copil are cate un colet, cu continut misterios, pe care doreste sa-l transporte la strada principala, care este axa OX, de unde va veni masina postei si il va lua. Pentru a putea face aceste transporturi, fiecare copil are cate o drona cu urmatoarele caracteristici:

  • v -> viteza cu care zboara aceasta ( v este exprimat in numarul de secunde necesare pentru a parcurge un metru)
  • h -> inaltimea la care trebuie sa zboare aceasta pentru a nu se strica
  • aceasta poate sa se deplaseze doar de-a lungul axelor. Din cauza vantului puternic, ea se poate deplasa doar in jos, adica spre o coordonata y mai mica. Astfel, ea poate merge doar pe directiile SUD, EST si VEST
  • d -> din cauza ca drona este teleghidata prin telecomanda aceasta nu poate sa se deplaseze la o distanta pe axa OX fata de casa mai mare ca d

Fiecare copil vrea sa afle timpul minim necesar transportarii coletului sau la strada principala. Deoarece copiii sunt prieteni buni intre ei, pentru a-si transporta coletul, un copil are doua optiunui: fie isi transporta coletul cu drona sa pana la strada principala, fie il transporta cu drona sa pana la un alt copil, care se va ocupa personal de colet si il va transporta pana la strada principala prin acelasi mod descris pana acum (ori il va transporta cu drona lui pana la strada principala, ori il va duce cu drona lui pana la alt copil care va face acelasi lucru si el). Timpul de schimbare al coletului de la o drona la alta este neglijabil, dar atentie ca drona trebuie urcata pana la un anumit nivel si apoi coborata la nivelul 0 cand ajunge la casa unui alt copil pentru ca acesta sa faca transferul de acea drona la a sa (cum am mentionat, cu timpul neglijabil).

Date de intrare

Fişierul de intrare colete.in contine pe prima linie numarul N. Pe urmatoarele N linii se afla cate 5 numere x, y, v, h, d cu semnificatiile din enunt.

Date de ieşire

În fişierul de ieşire colete.out trebuie sa se afle N linii, a i-a linie reprezentand timpul minim ca copilul i sa isi transporte coletul pana la strada principala.

Restricţii

  • 1 ≤ N ≤ 50000
  • 1 ≤ x, y, v, h, d ≤ 108
  • coordonatele y sunt distincte doua cate doua

Exemplu

colete.incolete.out
4
3 5 5 2 1
1 4 1 1 2
4 2 1 1 2
5 3 6 1 3
44
6
4
28
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?