O cursă de maşini electrice prevăzute cu panouri solare are loc pe un traseu care traversează n localităţi, numerotate în ordinea de pe traseu de la 1 la n. Linia de start se află la kilometrul zero şi coincide cu începutul primei localităţi. Linia de sosire este la sfârşitul ultimei localităţi. Orice localitate, exceptând localitatea 1, începe la sfârşitul localităţii precedente. Prin urmare, pentru fiecare localitate i se cunoaşte distanţa di de la linia de start până la sfârşitul localităţii, exprimată în km.
În momentul începerii competiţiei, din fiecare localitate există exact o maşină aliniată la linia de start. Maşinile au aceleaşi caracteristici, ca urmare se deplasează cu aceeaşi viteză, cu excepţia traversării localităţii din care provin unde, datorită avantajelor terenului propriu (suporteri dotaţi cu oglinzi, lămpi, etc...), îşi dublează instantaneu viteza până la ieşirea din localitate, apoi revin la viteza iniţială.
La concurs sunt invitate şi televiziunile locale, iar pentru telespectatori, sarea şi piperul sunt depăşirile, de aceea este important să reţinem informaţii despre acestea, pentru a le putea viziona în reluare. Se consideră depăşire situaţia în care o maşină ajunge din urmă o altă maşină, apoi trece în faţa acesteia.
Cerinţă
Cunoscând localităţile de pe traseu, scrieţi un program care tipăreşte ordinea sosirii maşinilor la linia de sosire, respectiv informaţii despre toate depăşirile efectuate în timpul concursului.
Date de intrare
Fişierul de intrare cursa1.in va conţine pe prima linie numărul de localităţi n. Urmează n linii care descriu informaţii despre cele n localităţi. Pe linia i+1 din fişier se află două numere naturale c şi d, separate prin spaţiu, cu semnificaţia că numărul de concurs al maşinii din localitatea i este c şi că localitatea i se termină la d kilometri faţă de linia de start.
Date de ieşire
Fişierul de ieşire cursa1.out va conţine pe prima linie numerele de concurs ale maşinilor în ordinea sosirii lor, separate prin câte un spaţiu. În cazul în care există mai multe maşini care sosesc simultan la linia de sosire, acestea vor fi afişate în ordinea crescătoare a numerelor de concurs. Pe următoarele linii sunt descrise depăşirile, în ordinea crescătoare a localităţilor în care se produc. O depăşire este descrisă printr-o succesiune de valori de forma L c k m1 m2... mk, cu semnificaţia că în localitatea L maşina cu numărul de concurs c depăşeşte k maşini, maşinile depăşite fiind, în ordinea în care sunt depăşite, m1 m2 ... mk. Dacǎ sunt depǎşite în acelaşi moment două sau mai multe maşini, acestea se vor afişa în ordinea descrescǎtoare a numerelor de concurs.
Restricţii
• 2 < n <= 500
• Numerele de concurs ale maşinilor sunt numere naturale nenule distincte de maxim 3 cifre.
• Distanţa dintre linia de start şi linia de sosire (sfârşitul ultimei localităţi) ≤ 30 000
• Dacă prima cerinţă este rezolvată corect, se obţine 40% din punctajul pe test. Dacă prima cerinţă este rezolvată corect, dar la afişarea depăşirilor maşinile dintr-o localitate nu sunt afişate în ordinea solicitată, se acordă 70% din punctajul pe test. Punctajul integral se obţine pentru rezolvarea corectă a ambelor cerinţe.
Prima localitate începe de la km.0 şi se termină la km.5 şi are maşina nr. 10. A doua localitate se află între km 5-7 şi are maşina nr. 66. A treia localitatea se află între km 7-15 şi are maşina nr. 99. A patra între km 15-23 are maşina nr. 35 şi ultima între km 23-34 are maşina 70.
Ordinea de sosire a maşinilor este: 70 35 99 10 66. Maşinile 35 şi 99 termină cursa deodată, se enumeră în ordinea crescătoare a numerelor.
Depăşiri: Localitatea 3: maşina 99 va depăşi 2 maşini, în ordine maşinile 66 apoi 10.
Localitatea 4: maşina 35 depăşeşte 2 maşini, pe 66 şi 10 şi ajunge pe 99 fără să o depăşească.
Localitatea 5: maşina 70 depăşeşte 4 maşini, în ordine pe 66, 10, apoi simultan pe 99 şi 35 aflate la egalitate (se enumeră în ordine descrescătoare).
