Fișierul intrare/ieșire	joc10.in, joc10.out	Sursă	OJI 2017 clasa a 7-a
Autor	Raluca Costineanu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.3 sec	Limită de memorie	65535 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Joc10 (clasa a 7-a)

Notă: problema este punctată ușor diferit față de original din cauza restricțiilor impuse de evaluatorul NerdArena.

Inspirați de clasicul joc Tic-Tac-Toe (X și 0), Teodora și Ștefan își propun să joace ceva asemănător, adăugând jocului clasic câteva reguli noi:

• tabla de joc este un pătrat de latură N, care este împărțit în NxN celule, așezate pe N linii și N coloane; celulele pătratului sunt numerotate de la 1 la N² parcurgând liniile de sus în jos, și coloanele de la stânga la dreapta;
• Teodora va marca celulele cu X (litera X), iar Ștefan cu 0 (cifra 0);
• în cadrul unei runde, copiii marchează alternativ câte o celulă din pătrat, nemarcată anterior;
• o rundă a jocului este descrisă printr-un șir format din exact N² numere naturale reprezentând celulele pătratului, în ordinea în care au fost marcate succesiv de cei doi copii;
• jocul are K runde; prima este începută de Teodora, a doua de Ștefan, a treia Teodora, a patra Ștefan și așa mai departe;
• o rundă este câștigată de jucătorul care reușește primul să marcheze complet o linie, o coloană, diagonala principală sau una din cele două semidiagonale paralele și alăturate cu aceasta (figura 1), diagonala secundară sau una din cele două semidiagonale paralele și alăturate acesteia (figura 2);
• o rundă se încheie fără un câștigător dacă după marcarea celor N² celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu același simbol.

Cerințe

Cunoscând numerele N, K și cele K șiruri de numere care reprezintă rundele jucate, scrieți un program care să rezolve una dintre următoarele două cerințe:

1. Să se determine câte runde a câștigat fiecare copil.
2. Să se determine care este cel mai mare număr de marcări efectuate până la câștigarea unei runde.

Date de intrare

Fișierul de intrare joc10.in conține pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe a doua linie se află două numere naturale N și K, separate prin câte un spațiu, reprezentând dimensiunea tablei de joc și respectiv numărul de runde jucate. Pe următoarele K linii sunt descrise rundele de joc, câte o rundă pe câte o linie a fișierului. În cadrul liniilor, numerele sunt separate prin câte un spațiu.

Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire joc10.out va conține pe prima linie două numere naturale t și s, separate printr-un spațiu, unde t reprezintă numărul de runde câștigate de Teodora, iar s numărul rundelor câștigate de Ștefan.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire joc10.out va conține pe prima linie numărul cel mai mare de marcări efectuate până la câștigarea unei runde.

Restricții

• 3 ≤ N ≤ 100
• 1 ≤ K ≤ 25
• La fiecare joc se câștigă cel puțin o rundă.
• Pentru rezolvarea corectă a primei cerințe se acordă 45 50 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 50 de puncte. Se acordă 10 puncte din oficiu.

Exemplul 1

Explicație

Runda 1	Runda 2	Runda 3	Runda 4
Începe Teodora. Câștigă Teodora după 7 marcări.	Începe Ștefan. Câștigă Teodora după 14 marcări.	Începe Teodora. Câștigă Ștefan după 8 marcări.	Începe Ștefan. Nu câștigă nici un jucător

Exemplul 2

Explicație

Doar 3 dintre cele 4 runde jucate au fost câștigate. Până în momentul câștigării în prima rundă s-au făcut 7 marcări, în a doua 14, iar în a treia 8. Deci numărul maxim de marcări făcute până la câștigarea unei runde este 14.