Vizualizare sursă pentru „0317 - SumMax”

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

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

= Date de ieşire =
Fişierul de ieşire <code>summaxOUT.txt</code> va conţine pe prima linie numărul <code>S</code>, 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 =

* <code>1 ≤ n ≤ 10</code>
* elementele matricei vor avea cel mult <code>4</code> cifre

= Exemplul 1 =
<code>summaxIN.txt</code>
 4
 12 16 5 4
 11 14 6 7
 8 2 3 17
 10 9 13 15
<code>summaxOUT.txt</code>
 57

== Explicație ==
<code>57=16+11+17+13</code>.

= Exemplul 2 =
<code>summaxIN.txt</code>
 100000
consola
 Nu corespunde restricțiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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'))

</syntaxhighlight>