Fişierul intrare/ieşire:run.in, run.outSursăConcurs Shumen juniori 2013
AutorAutor NecunoscutAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test3 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Run (clasa a 8-a)

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ă Si. 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 cât mai bună.

Cerinţă

Să se determine ordinea în care concurenţii vor fi eliminaţi. 

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

  • N ≤ 500 000
  • L ≤ 5 000 000
  • 0 ≤ D1 < D2 < D3 < ... < DN < L
  • 0 < Si ≤ 5 (numere reale cu exact două zecimale)

Exemplu

run.inrun.out
6 150
0 1.75
30 0.80
60 0.50
70 1.00
120 0.10
140 0.90
2
3
5
4
6
Winner(s): 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici