2054 - Joc 7

Enunt

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 N*N celule, așezate pe N linii și N coloane; celulele pătratului sunt numerotate de la 1 la N^2 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^2 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, diagonala secundară sau una din cele două semidiagonale paralele și alăturate acesteia; o rundă se încheie fără un câștigător dacă după marcarea celor N^2 celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu același simbol.

Cerinţa

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:

Să se determine câte runde a câștigat fiecare copil. 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 joc7.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 joc7.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 joc7.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 şi precizări

• 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 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

joc7.in

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

joc7.out

2 1

Explicație

Ilustrarea rundelor de joc până la momentul identificării unui câștigător este următoarea:

• Runda 1 (începe Teodora): Runda este câștigată de Teodora după 7 marcări. Se completează semidiagonala situată sub diagonala principală.
• Runda 2 (începe Ştefan): Runda este câştigată de Teodora după 14 marcări. Se completează semidiagonala situată sub diagonala secundară.
• Runda 3 (începe Teodora): Runda este câştigată de Ștefan după 8 marcări. Se completează linia a doua.
• Runda 4 (începe Ştefan): Runda nu este câştigată de niciun jucător.

Exemplul 2

joc7.in

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

joc7.out

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.

Rezolvare

def check_winner(board, N):
    # Verificăm liniile și coloanele
    for i in range(N):
        if all(board[i][j] == board[i][0] and board[i][0] != '.' for j in range(N)):
            return True
        if all(board[j][i] == board[0][i] and board[0][i] != '.' for j in range(N)):
            return True
    
    # Verificăm diagonala principală
    if all(board[i][i] == board[0][0] and board[0][0] != '.' for i in range(N)):
        return True
    
    # Verificăm diagonala secundară
    if all(board[i][N-1-i] == board[0][N-1] and board[0][N-1] != '.' for i in range(N)):
        return True
    
    return False

def max_marks_per_round(rounds):
    max_marks = 0
    for round in rounds:
        max_marks = max(max_marks, len(round))
    return max_marks

def main():
    C = int(input().strip())
    N, K = map(int, input().strip().split())
    rounds = [input().strip().split() for _ in range(K)]
    
    if C == 1:
        # Numărăm câte runde a câștigat fiecare copil
        teodora_wins = 0
        stefan_wins = 0
        for round in rounds:
            board = [['.' for _ in range(N)] for _ in range(N)]
            for i, mark in enumerate(round):
                row = (int(mark) - 1) // N
                col = (int(mark) - 1) % N
                if i % 2 == 0:
                    board[row][col] = 'X'
                else:
                    board[row][col] = 'O'
            if check_winner(board, N):
                if len(round) % 2 == 1:
                    teodora_wins += 1
                else:
                    stefan_wins += 1
        
        print(teodora_wins, stefan_wins)
    elif C == 2:
        # Determinăm cel mai mare număr de marcați efectuate până la câștigarea unei runde
        max_marks = max_marks_per_round(rounds)
        print(max_marks)

if __name__ == "__main__":
    main()