Zadatak: Rubik

40 bodova, Državno natjecanje iz informatike, Algoritmi, 8. razred, 1. zadatak

Na svjetskom prvenstvu u slaganju Rubikove kocke nastupa N natjecatelja označenih brojevima od 1 do N. Među njima je i Zrinka, naša prvakinja. Natjecatelji kocku redom slažu od prvog do N-tog i za svakog natjecatelja bilježimo u kojem je vremenu složio kocku. Oni natjecatelji koji je ne uspiju složiti u 120 sekundi, za njih bilježimo postotak složenosti kocke u 120. sekundi. Ljestvica poretka se slaže prema brzini slaganja kocke od onih bržih prema onim sporijima, a oni koji je nisu uspjeli složiti u 120 sekundi slažu se na istoj ljestvici prema postotku složenosti kocke od većeg prema manjem. Ako dvoje ili više natjecatelja imaju isto vrijeme slaganja ili isti postotak složenosti, bolje mjesto zauzima osoba s manjom oznakom. Uvijek će postojati natjecatelj koji je složio kocku u vremenu manjem od 120 sekundi. Tijekom natjecanja, natjecatelj koji je trenutno vodeći u poretku, stoji na postolju najboljeg i čeka da netko bude brži/bolji od njega i da ga zamjeni na tom mjestu. Ako znamo da Zrinka ima oznaku K, odgovori na sljedeća četiri pitanja. Prvo pitanje: U kojem je vremenu pobjednik natjecanja složio Rubikovu kocku? Drugo pitanje: Koji je natjecatelj zauzeo posljednje mjesto? Treće pitanje: Koje je mjesto zauzela Zrinka? Četvrto pitanje: Koji je natjecatelj najdulje stajao na postolju najboljeg? Vrijeme provedeno na postolju mjeri se brojem natjecatelja koji su nastupili nakon njega, a nisu uspjeli biti brži/bolji od njega. Ako je više natjecatelja stajalo na postolju isto vrijeme, ispiši onog s manjom oznakom.

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 100), broj iz teksta zadatka. U drugom je retku prirodan broj K (1 ≤ K ≤ N), broj iz teksta zadatka. U sljedećih N redaka nalaze se po dva prirodna broja Ti – vrijeme u sekundama u kojem je i-ti natjecatelj složio kocku i Pi - postotak složenosti kocke u Ti sekundi. Ako je Ti između 1 i 119, tada je Pi uvijek 100, a ako je Ti jednak 120 tada je Pi između 1 i 99.

IZLAZNI PODACI

U prvi redak ispiši prirodan broj, odgovor na prvo pitanje iz teksta zadatka. U drugi redak ispiši prirodan broj, odgovor na drugo pitanje iz teksta zadatka. U treći redak ispiši prirodan broj, odgovor na treće pitanje iz teksta zadatka. U četvrti redak ispiši prirodan broj, odgovor na četvrto pitanje iz teksta zadatka.

BODOVANJE

Točan ispis svakog od četiri retka vrijedi 1 bod za svaki testni primjer. U primjerima vrijednima 12 bodova svi će natjecatelji složiti kocku. U primjerima vrijednima 8 bodova, Zrinka će nastupiti prva.

Primjeri test podataka

Ulaz

3
2
100 100
110 100
120 90

Izlaz

100
3
2
1

Ulaz

4
3
90 100
95 100
110 100
120 80

Izlaz

90
4
3
1

Ulaz

5
4
110 100
110 100
115 100
118 100
119 100

Izlaz

110
5
4
1