Naloga: 2003.3.2-Smučarji
Celotna pola iz tekmovanja je dosegljiva na:
Na posamezni smučarski tekmi za svetovni pokal dobi vsak tekmovalec določeno število točk (0 ali več). Število prejetih točk je odvisno od njegove uvrstitve na tej tekmi. Mednarodna smučarska zveza vodi tudi razvrstitev v skupnem seštevku, kjer je vsak tekmovalec predstavljen z vsoto točk, ki jih je dobil na vseh tekmah trenutne sezone. Ko manjka do konca sezone le še ena tekma, se opazovalci radi sprašujejo, katera je najslabša ali najboljša možna uvrstitev v skupnem seštevku, ki bi jo nek tekmovalec utegnil dobiti po zadnji tekmi. Recimo na primer, da se na posamezni tekmi dobi 100 točk za prvo mesto, 50 za drugo, 25 za tretje, za ostala pa še manj. Recimo še, da v skupnem seštevku trenutno vodi tekmovalec A, drugo uvrščeni pa je tekmovalec B, ki za A-jem zaostaja za 60 točk. Iz tega že lahko sklepamo, da bo A po zadnji tekmi v skupnem seštevku ali prvi ali drugi, gotovo pa ne slabši. Da bi ga kdo v skupnem seštevku prehitel, bi namreč potreboval vsaj 60 točk, toliko pa lahko na eni tekmi dobi samo zmagovalec. Torej lahko A-ja v skupnem seštevku prehiti največ en tekmovalec (zmagovalec zadnje tekme, če se A na njej uvrsti dovolj slabo). Tvoj program bo v vhodni datoteki dobil naslednje podatke. (Vsi podatki so cela števila, vsako je v samostojni vrstici, okoli njih ni presledkov, praznih vrstic ali česa podobnega.)
- V prvi vrstici je m, število smučarjev, ki na posamezni tekmi dobijo kaj točk. Tisti, ki se uvrstijo na (m + 1)-vo ali slabše mesto, ne dobijo nič točk.
- V naslednjih m vrsticah je za vsako uvrstitev od prve do m-te podano število točk, ki jih dobi tekmovalec za to uvrstitev. Če število točk, ki jih prejme i-to uvrščeni, označimo s ti, lahko predpostaviš, da velja: 100 000 ≥ t_1 > t_2 > t_3 > • • • > t_m−1 > t_m > 0.
- V naslednji vrstici je n, število smučarjev v skupnem seštevku svetovnega pokala.
- V naslednjih n vrsticah je podano za vsakega od teh smučarjev njegovo število točk v skupnem seštevku pred zadnjo tekmo sezone; najprej za vodilnega v skupnem seˇstevku, nato za drugega, itd., nazadnje pa za zadnjega. Če je ai število točk, ki jih ima i-ti najboljši v skupnem seštevku, lahko predpostaviš, da velja: 100 000≥a_1≥a_2≥a_3 • • •≥a_n−≥ a_n ≥0.
Tako m kot n sta pozitivni celi števili, ki nista manjši od 1 in nista večji od 3 000. V izhodno datoteko naj tvoj program zapiše n vrstic. V vsaki naj bosta dve pozitivni celi števili. Prvo število v i-ti vrstici naj bo najboljši možni položaj, ki ga bi utegnil imeti v skupnem seštevku po zadnji tekmi tisti tekmovalec, ki je v skupnem seštevku pred zadnjo tekmo na i-tem mestu. Drugo število v i-ti vrstici naj bo najslabši možni položaj, ki bi ga utegnil imeti ta tekmovalec v skupnem seštevku po zadnji tekmi. Dogovorimo se še, da na zadnji tekmi sezone velja posebno pravilo: ne more se zgoditi, da bi si dva ali več tekmovalcev delilo isto mesto (torej tudi ne morejo dobiti enakega števila točk). Če bi imelo več tekmovalcev na stotinko enak čas, jih bodo pač razvrstili s pomočjo žreba in zakulisne kuhinje. (Lahko pa si več ljudi deli mesto v skupnem seštevku. Če sta dva sedma, je tisti takoj za njima deveti in podobno.) Mogoče pa je, da kak tekmovalec (lahko celo zelo veliko tekmovalcev) med tekmo odstopi (ali pa sploh ne štartajo ali pa so diskvalificirani) in takšni ne dobijo na tej tekmi nobenih točk.
Primer vhodne datoteke:
6
50
25
20
10
5
3
10
1000
980
971
930
925
923
920
915
912
910
Pripadajoča izhodna datoteka:
1 3
1 3
1 4
2 8
3 10
3 10
4 10
4 10
4 10
4 10
