0961 - Criptare

Cerinţa

După dezastrul cauzat de hackerul Gigel ( #Suprasolicitare ), administratorul rețelei s-a decis să ia măsuri.

Acesta este responsabil de o rețea cu n*n calculatoare dispuse sub forma unei matrice cu n linii și n coloane, în care fiecare calculator este conectat la calculatoarele adiacente(sus, dreapta, stânga, jos), fiecare calculator de pe rândul n este conectat la calculatorul de pe rândul 1 și aceeași coloană, și fiecare calculator de pe de pe coloana n este conectat la cel de pe coloana 1 și aceeași linie.

În această rețea, există calculatoare criptate, care nu pot primi pachete de date corupte. Calculatoarele necriptate pot primi pachete corupte dar nu le pot prelucra. Comportamentul lor este unul aparte: când un calculator necriptat primește un pachet de date, îl transmite mai departe la următorul calculator pe aceeași direcție până întâlnesc un calculator criptat. Calculatorul care conține pachetul de date corupt poate primi apoi o comandă prin care să îl transmită mai departe în altă direcție.

Rețeaua devine suprasolicitată dacă pachetul corupt ajunge pe o linie sau coloană care conține numai calculatoare necriptate, putându-se astfel să se transmită la infinit.

Hackerul Gigel a profitat de această slăbiciune a rețelei și a reușit dea comenzi prin terminalele calculatoarelor astfel încât pachetul de date să se transmită la infinit între ele, suprasolicitând rețeaua, (vezi problema #Suprasolicitare ).

Administratorul rețelei a decis să cripteze suficiente calculatoare pentru a evita orice posibilitate de suprasolicitare a rețelei. Deoarece criptarea unui singur calculator ia mult timp, administratorul dorește să afle numărul minim de calculatoare care trebuie criptate astfel încât hackerul Gigel să nu se mai poată distra cu rețeaua.

Date de intrare

Fișierul de intrare criptare.in conține pe prima linie numărul n, urmat de n rânduri cu n numere. Valoarea 1 reprezentă un calculator deja criptat, iar valoarea 0 un calculator necriptat.

Date de ieşire

Dacă datele sunt introduse corect,în fişierul de ieşire criptare.out se va afișa :"Datele sunt introduse corect.",apoi pe un rând va conţine numărul Sol, reprezentând numărul minim de calculatoare ce necesită a fi criptate, iar pe următoarele Sol rânduri o pereche de numere x și y reprezentând că pe linia x și coloana y calculatorul trebuie criptat.În cazul contrar,se va afișa pe ecran "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 1 ⩽ n ⩽ 1000
• Orice soluție cu număr minim de calculatoare criptate este corectă.
• Pentru afișarea doar a lui Sol, se acordă 20% din punctaj
• Pentru teste în valoare de 40 de puncte, n ≤ 10.

Exemplu

criptare.in

5

0 0 0 0 0

1 1 1 1 1

1 0 1 1 0

0 1 0 1 0

0 0 0 0 0

criptare.out

Datele sunt introduse corect.

2

1 1

5 3

Explicație

După criptarea calculatoarelor (1,1) și (5,3), hackerul Gigel nu mai poate trimite pachetul la infinit pe linia 1, respectiv linia 5

Rezolvare

# Funcție care verifică dacă datele de intrare sunt valide
def validare_date(n: int, a: list[list[int]]) -> bool:

    if n < 1 or n > 1000:
        return False
    for i in range(n):
        if len(a[i]) != n:
            return False
        for j in range(n):
            if a[i][j] not in [0, 1]:
                return False
    return True

# Funcție care calculează numărul minim de calculatoare care trebuie criptate astfel încât hackerul Gigel să nu se mai
# se poată distra cu rețeaua.
def criptare(n: int, a: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:
    L, C = [], []
    for i in range(n):
        linie_criptata = any(a[i][j] for j in range(n))  # verifică dacă există cel puțin un element 1 în linia i
        coloana_criptata = any(a[j][i] for j in range(n))  # verifică dacă există cel puțin un element 1 în coloana i
        if not linie_criptata:
            L.append(i + 1)  # adaugă linia i+1 la lista L dacă aceasta nu are niciun element 1
        if not coloana_criptata:
            C.append(i + 1)  # adaugă coloana i+1 la lista C dacă aceasta nu are niciun element 1
    numar_calculatoare_criptate = max(len(L), len(C))  # determină numărul minim de calculatoare care trebuie criptate
    puncte_criptare = [(L[i], C[i]) for i in range(min(len(L), len(C)))]  # perechile (linie, coloană) pentru primele L sau C elemente
    if len(L) > len(C):
        for i in range(len(C), len(L)):
            puncte_criptare.append((L[i], 1))  # adaugă perechi (linie, 1) pentru fiecare element L care nu are corespondent în C
    elif len(C) > len(L):
        for i in range(len(L), len(C)):
            puncte_criptare.append((1, C[i]))  # adaugă perechi (1, coloană) pentru fiecare element C care nu are corespondent în L
    return numar_calculatoare_criptate, puncte_criptare


#Programul principal
if __name__ == '__main__':
    with open('criptare.in', 'r') as fin:
        n = int(fin.readline().strip())
        a = [list(map(int, fin.readline().split())) for _ in range(n)]
    if validare_date(n, a):
        numar_calculatoare_criptate, puncte_criptare = criptare(n, a)
        with open('criptare.out', 'w') as fout:
            fout.write("Datele sunt introduse corect.\n")
            fout.write(str(numar_calculatoare_criptate) + '\n')
            for Sol in puncte_criptare:
                fout.write(str(Sol[0]) + ' ' + str(Sol[1]) + '\n')
    else:
        with open('criptare.out', 'w') as fout:
           fout.write("Datele nu corespund restricțiilor impuse.")