Diferențe pentru problema/run între reviziile #17 si #33

run

Run (clasa a 8-a)

== include(page="template/taskheader" task_id="run") ==

Pete l-a provocat pe Stan să participe la așa numitul "maraton ciclic". Maratonul ciclic are cateva reguli. Pista este circulară și are lungimea L. Pe pistă se fixează punctul START/SOSIRE. Fiecare concurent primește un numar de la _1_ la _N_ și se așează la o distanță _D_ fata de punctul de START, in direcția acelor de ceasornic. Cand se dă startul, concurenții încep aleargarea, fiecare avînd o anumită viteză S[~i~]. Dacă un concurent ajunge un altul din urmă, îl atinge și îl elimină.

Pete l-a provocat pe Stan să participe la așa numitul "maraton ciclic". Maratonul ciclic are câteva reguli. Pista este circulară și are lungimea _L_. Pe pistă se fixează punctul START/SOSIRE. Fiecare concurent primește un număr de la _1_ la _N_ și se așază la o distanță _D_ față de punctul de START, în direcția acelor de ceasornic. Când se dă startul, concurenții încep alergarea, fiecare având o anumită viteză _S[~i~]_. Dacă un concurent ajunge un altul din urmă, îl atinge și îl elimină.

Concursul se termină cînd nu mai pot fi eliminați concurenți. Toți cei care rămîn pe pistă sunt declarați cîștigători. Stan a acceptat provocarea dar ar dori să-și crească șansa de a cîștiga, alegîndu-și o poziție de start cat mai buna. Să se determine ordinea în care concurenții vor fi eliminați.

Concursul se termină când nu mai pot fi eliminați concurenți. Toți cei care rămân pe pistă sunt declarați câștigători. Stan a acceptat provocarea dar ar dori să-și crească șansa de a câștiga, alegându-și o poziție de start cât mai bună.
 
h2. Cerință
 
Să se determine ordinea în care concurenții vor fi eliminați.

h2. Date de intrare

Fișierul de intrare $run.in$ contine pe prima linie numerele naturale _N_ si _L_. Pe fiecare din liniile următoare găsim distanța concurentului _i_ fata de START si viteza cu care aleargă acesta. Distanțele sunt exprimate in metri iar vitezele in metri/secundă.

Fișierul de intrare $run.in$ conține pe prima linie numerele naturale _N_ si _L_. Pe fiecare din liniile următoare găsim distanța concurentului _i_ față de START și viteza cu care aleargă acesta. Distanțele sunt exprimate în metri, iar vitezele în metri/secundă. Distanțele sunt numere întregi iar vitezele sunt numere reale cu exact două zecimale.

h2. Date de ieșire

În fișierul de ieșire $run.out$ se afișează pe linii distincte numărul de ordine al concurenților eliminați. Pe ultima linie linie se afișează  ”Winner(s):” si lista cîștigătorilor, în ordine crescătoare cu un spatiu între numerele de ordine.

În fișierul de ieșire $run.out$ se afișează pe linii distincte numerele de ordine ale concurenților eliminați. Dacă doi sau mulți concurenți sunt eliminați simultan, atunci aceștia pot fi afișați în orice ordine. Pe ultima linie linie se afișează $"Winner(s):"$ și lista câștigătorilor, în ordine crescătoare cu un spațiu între numerele de ordine.

h2. Restricții
* $N ≤ 500 000$
* $L ≤ 5 000 000$

* $0 ≤ D[~1~] ≤ D[~2~] ≤ ... ≤ D[~N~] ≤ L$
* $0 < S[~i~] &le; 5 (numere reale cu două zecimale)$

* $0 &le; D[~1~] < D[~2~] < D[~3~] < ... < D[~N~] < L$
* $0 < S[~i~] &le; 5$ (numere reale cu exact două zecimale)

h2. Exemplu

|_. run.in |_. run.out |
| 6 150
0 1.75

30 0.8
60 0.5
70 1
120 0.1
140 0.9

30 0.80
60 0.50
70 1.00
120 0.10
140 0.90

| 2
3
5

Winner(s): 1
|

h3. Explicație
 
...

== include(page="template/taskfooter" task_id="run") ==