Državna razina / Primjena algoritama OŠ 2022. / Osnovna škola (6. razred) - 3. zadatak

Nakon burne i zabavne noći, učenici jednog već poznatog razreda sjetno se prisjećaju sretnijih dana kada su se igrali glazbenih stolica na satu latinskog jezika. Igru glazbenih stolica igra N igrača označenih s prvih N prirodnih brojeva, te se na početku svaki igrač nalazi pokraj stolice označene istim brojem. Stolice su poredane u krug u smjeru kazaljke na satu. Dok glazba svira svaki se igrač kružno giba u smjeru kazaljke na satu, brzinom potrebnom da razmak između dvije uzastopne stolice prijeđe za jednu sekundu. Nakon zaustavljanja glazbe, svaki igrač koji se u tom trenutku nalazi neposredno pored prazne stolice sjeda na nju, dok se ostatak igrača nastavlja gibati dokgod ne naiđu i oni na praznu stolicu. Naravno, postoji kvaka! Neposredno prije zaustavljanja glazbe iz kruga se miče jedna stolica, pritom ne mijenjajući raspored ostalih stolica, drugim riječima, igračima će za prelazak udaljenosti između nekih parova uzastopnih stolica sada trebati više od jedne sekunde. Igrač koji ne uspijeva sjesti na stolicu ispada iz igre, te se igra nastavlja s jednim igračem manje. Napiši program koji će za svako od N-1 puštanja glazbe ispisati koji je igrač izbačen nakon toga.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 20), broj igrača iz teksta zadatka. U sljedećih se N-1 redaka nalaze parovi brojeva Ti (1 ≤ Ti ≤ 100) te Si (1 ≤ Si ≤ N), duljina trajanja glazbe prilikom i-tog puštanja, te oznaka stolice koja je prije toga maknuta.

Izlazni podaci

U sljedećih N-1 redaka potrebno je za svako puštanje glazbe ispisati koji je igrač nakon toga izbačen.

Bodovanje

U primjerima vrijednim 50 bodova vrijedit će Ti = 1. Točno ispisanih prvih X redaka u testnom primjeru vrijedit će X bodova.

Primjer zadatka

Ulaz

5
5 3
1 5
2 4
1 1

Izlaz

3
4
5
1

Ulaz

4
4 3
5 4
5 1

Izlaz

3
2
1

Ulaz

7
6 1
1 7
1 3
4 4
3 6
3 2

Izlaz

2
7
1
3
5
4

Opis prvog probnog primjera:

Igru igra pet osoba. Promotrimo tijek igre na sličicama.