0317 - SumMax

Cerinţa

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere naturale distincte. Determinaţi cea mai mare sumă a n elemente din matrice, cu proprietatea că oricare două elemente se află pe linii şi coloane distincte.

Date de intrare

Fişierul de intrare summaxIN.txt conţine pe prima linie numărul n, iar pe următoarele n linii câte n numere naturale, separate prin spaţii, reprezentând elementele matricei.

Date de ieşire

Fişierul de ieşire summaxOUT.txt va conţine pe prima linie numărul S, reprezentând suma maximă determinată. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricţii şi precizări

• 1 ≤ n ≤ 10
• elementele matricei vor avea cel mult 4 cifre

Exemplul 1

summaxIN.txt

4
12 16 5 4
11 14 6 7
8 2 3 17
10 9 13 15

summaxOUT.txt

57

Explicație

57=16+11+17+13.

Exemplul 2

summaxIN.txt

100000

consola

Nu corespunde restricțiilor

Rezolvare

def citeste_matrice(file_path):
    with open(file_path, 'r', encoding='utf-8') as file:
        n = int(file.readline().strip())
        matrice = [list(map(int, file.readline().split())) for _ in range(n)]
    return n, matrice

def scrie_rezultat(file_path, rezultat):
    with open(file_path, 'w', encoding='utf-8') as file:
        file.write(str(rezultat))

def verifica_restrictii(n, matrice):
    if not (1 <= n <= 10):
        return False

    for linie in matrice:
        for element in linie:
            if not (0 <= element <= 9999):
                return False

    return True

def gaseste_suma_maxima(n, matrice):
    elemente_sortate = sorted([(matrice[i][j], i, j) for i in range(n) for j in range(n)], reverse=True)

    linii_selectate = set()
    coloane_selectate = set()

    suma_maxima = 0

    for element, i, j in elemente_sortate:
        if i not in linii_selectate and j not in coloane_selectate:
            suma_maxima += element
            linii_selectate.add(i)
            coloane_selectate.add(j)

    return suma_maxima

if __name__ == "__main__":
    fisier_intrare = "summaxIN.txt"
    fisier_iesire = "summaxOUT.txt"

    n, matrice = citeste_matrice(fisier_intrare)

    if verifica_restrictii(n, matrice):
        rezultat = gaseste_suma_maxima(n, matrice)
        if rezultat > 0:
            scrie_rezultat(fisier_iesire, rezultat)
        else:
            scrie_rezultat( "Nu corespunde restrictiilor".encode('utf-8'))
    else:
        scrie_rezultat(fisier_iesire, "Nu corespunde restricțiilor".encode('utf-8').decode('utf-8'))