Žušanijsko natjecanje 2020. godine za 1. i 2. razred Srednje Škole - 3. zadatak

Mirko i Slavko igraju poznatu igru križić-kružić na n × n ploči. Pravila igre svi znamo: počevši od prazne ploče, u njezina polja naizmjence upisuju znakove X tj. križić (Mirko) i O tj. kružić (Slavko). Kada netko skupi n svojih znakova u istom redu, u istom stupcu ili na istoj dijagonali ploče, on je pobjednik igre. Nakon toga igrači, ako žele, i dalje mogu upisivati znakove na ploču, ali ishod igre se ne mijenja, tj. drugi igrač više ne može pobijediti čak ni ako skupi svojih n znakova u nizu.

U ovom zadatku ne pretpostavljamo ništa o tome kako igrači igraju, dakle ne igraju nužno najbolje poteze. Moguće je i da su posve dekoncentrirani pa da igraju iznimno loše jer usput rješavaju matematičke zadatke.

Zadan je niz poteza od početka igre (od prazne ploče). Svaki potez opisan je kao par red, stupac, a prvi na potezu je Mirko (križić) i dalje se izmjenjuju. Igra nakon ovih poteza možda je završila, a možda još nije, no vaš je zadatak ispisati ishod u tom trenutku igre i to na sljedeći način: • “X” (veliko slovo iks) – ako je Mirko (križić) već pobijedio, tj. prvi skupio n znakova u nizu, • ”O” (veliko slovo O) – ako je Slavko (kružić) već pobijedio, tj. prvi skupio n znakova u nizu, • ”N” (kao "Neriješeno") – ako nema pobjednika i teoretski više nitko ne može pobijediti, • ”NX” k – ako još nema pobjednika, ali Mirko (križić) još bi mogao pobijediti i to najranije nakon k idućih poteza, • ”NO” k – ako još nema pobjednika, ali Slavko (kružić) još bi mogao pobijediti i to najranije nakon k idućih poteza, • ”NXO” k1 k2 – ako još nema pobjednika, ali Mirko (križić) mogao bi pobijediti najranije nakon k1 idućih poteza, a u drugačijem scenariju Slavko (kružić) mogao bi pobijediti najranije nakon k2 idućih poteza.

Napomene. Zadani niz poteza bit će ispravan, tj. u svako polje ploče bit će upisan najviše jedan znak. Moguće je da su oba igrača već skupili n svojih znakova u nizu (za ishod je relevantno tko je to prvi učinio). Ishodi se ispisuju bez navodnika. U broj poteza (k) računamo poteze obojice igrača, npr. jedan potez Mirka i jedan potez Slavka brojimo kao dva poteza. Vodite računa o tome koji je igrač na potezu nakon zadanog niza poteza. Pogledajte donje primjere i njihova pojašnjenja radi boljeg razumijevanja zadatka.

ULAZNI PODACI

U prvom je retku prirodan broj n iz skupa {3, 4, 5}, dimenzija ploče.

U prvom je retku cijeli broj m (0 ≤ m ≤ n^2 ), broj odigranih poteza.

Ako je m > 0, u svakom od sljedećih m redaka nalaze se prirodni brojevi r i s (1 ≤ r, s ≤ n) red i stupac polja u koje je igrač na potezu upisao svoj znak.

IZLAZNI PODACI

U prvi i jedini redak ispišite traženi ishod igre kao niz od 1-3 slova nakon kojeg u nekim slučajevima slijedi prirodan broj (ili dva) odvojen razmakom, kao što je definirano u tekstu zadatka.

PRIMJERI TEST PODATAKA

ulaz

3
0

izlaz

NXO 5 6

ulaz

3
7
2 1
3 1
1 2
3 2
2 2
3 3
1 3

izlaz

O

ulaz

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

izlaz

NX 6

Objašnjenje

U prvom primjeru odigrano je nula poteza (ploča je prazna) i na potezu je križić. Uz lošu igru protivnika, on u najboljem slučaju može složiti svoja tri znaka u nizu nakon 5 poteza (od kojih su tri njegova, a dva protivnička). Kružiću to može uspjeti nakon 6 poteza (od kojih su tri protivnička, a tri njegova).

U drugom primjeru kružić je nakon šest odigranih poteza već pobijedio skupivši svoja tri znaka u trećem redu. (Uočite da je na izlazu slovo O, a ne broj 0, kao i u prvom primjeru!)

U trećem primjeru, nakon sedam odigranih poteza na potezu je kružić, ali kako god igrali, on više ne može pobijediti. Križić može pobijediti nakon šest poteza (tri protivnička i tri njegova).