Fişierul intrare/ieşire:joc10.in, joc10.outSursăOJI 2017 clasa a 7-a
AutorRaluca CostineanuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie65535 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Joc10 (clasa a 7-a)

Notă: problema este punctată uşor diferit faţă de original din cauza restricţiilor impuse de evaluatorul infoarena.

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 N2 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 N2 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 N2 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

joc10.injoc10.out
1
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13
2 1

Explicaţie

Runda 1Runda 2Runda 3Runda 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

joc10.injoc10.out
2
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13
14

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici