Editing 2741 - SAO1

==Enunț==
După ce ți-ai dat seama că nu poți învinge nici unul dintre monștrii (din problema SAO), ai decis să te retragi și să devii un fermier. Din banii pentru cumpărarea echipamentului ai cumpărat o parcelă codificată sub forma unei matrice de n linii și m coloane, pentru fiecare zonă cunoscându-se fertilitatea ei. Cum nu ai bani ca să cultivi pământul, dorești să selectezi o parcelă în care toate zonele să aibă aceeași fertilitate, iar fertilitatea totală să fie maximă. Fertilitatea totală a unei parcele este egală cu suma fertilităților zonelor care compun acea parcelă.

==Cerința==
Dându-se matricea codificărilor zonelor din teren, să se determine fertilitatea totală maximă a unei parcele în care toate zonele au aceeași fertilitate.

==Date de intrare==
Fișierul de intrare sao1.in conține pe prima linie numerele n şi m, iar pe următoarele n linii câte m numere naturale, separate prin spaţii, reprezentând elementele matricei.

==Date de ieșire==
Fișierul de ieșire sao1.out va conține numărul P, reprezentând fertilitatea totală maximă a unei parcele, în condițiile date.

==Restricții și precizări==

1 ≤ n,m ≤ 500
fertilitatea totală se va încadra pe tipul de date long long.
nu există sol infertil (a cărui fertilitate să fie mai mică sau egală cu 0).
acesta este “bad ending”-ul problemei SAO

==Exemplu==
===Exemplu1===
 
SAO1.in
<syntaxhighlight lang="python">
4 4
1 1 1 3
1 1 1 3
1 1 1 3
3 3 3 3
</syntaxhighlight>

SAO1.out
<syntaxhighlight lang="python">
21
</syntaxhighlight>

===Exemplu2===
SAO1.in
<syntaxhighlight lang="python">
4 4
3 5 1 3
1 5 5 3
5 5 5 3
3 3 3 3
</syntaxhighlight>

SAO1.out
<syntaxhighlight lang="python">
30
</syntaxhighlight>

==Rezolvare==
 <syntaxhighlight lang="python">
 
def validare(n, m, matrice):
    # verificam daca dimensiunile matricei sunt in intervalul permis
    if n < 1 or n > 500 or m < 1 or m > 500:
        return False
    # verificam ca toate valorile din matrice sa fie numere intregi pozitive
    for i in range(n):
        for j in range(m):
            if not matrice[i][j].isdigit() or int(matrice[i][j]) <= 0:
                return False
    return True


def rezolvare(n, m, matrice):
    # initializam suma maxima cu 0
    suma_maxima = 0
    # cautam valoarea maxima din matrice
    max_valoare = int(matrice[0][0])
    for i in range(n):
        for j in range(m):
            valoare = int(matrice[i][j])
            if valoare > max_valoare:
                max_valoare = valoare
    # iteram prin valori de la 1 la valoarea maxima din matrice
    for k in range(1, max_valoare + 1):
        suma = 0
        # calculam suma pentru fiecare submatrice care contine doar valoarea k
        for i in range(n):
            for j in range(m):
                if matrice[i][j] == str(k):
                    suma += k
        # actualizam suma_maxima daca suma este mai mare
        if suma > suma_maxima:
            suma_maxima = suma
    return suma_maxima


def main():
    # citim datele de intrare din fisierul "sao1.in"
    with open("sao1.in") as f:
        n, m = map(int, f.readline().split())
        matrice = [f.readline().split() for i in range(n)]

    # validam datele de intrare
    if not validare(n, m, matrice):
        print("Date de intrare invalide")
        return

    # rezolvam problema
    suma_maxima = rezolvare(n, m, matrice)

    # afisam rezultatul in fisierul "sao1.out"
    with open("sao1.out", "w") as f:
        f.write(str(suma_maxima))


if __name__ == "__main__":
    main()


</syntaxhighlight>

==Explicații ==
ACodul începe prin citirea datelor de intrare din fișierul "sao1.in" în funcția "validare". În această funcție, se verifică dacă datele de intrare respectă restricțiile problemei: 1 ≤ n,m ≤ 500 și dacă fertilitatea tuturor zonelor este strict pozitivă.

În funcția "rezolvare", se calculează fertilitatea maximă a unei parcele în care toate zonele au aceeași fertilitate. Algoritmul folosit este unul de tip căutare binară. Se găsește cea mai mică fertilitate posibilă, iar apoi se calculează fertilitatea totală a unei parcele în care toate zonele au aceeași fertilitate, folosind această fertilitate minimă ca și valoare pentru toate zonele. Dacă fertilitatea totală calculată este mai mică decât suma fertilităților tuturor zonelor, se scade valoarea 1 din fertilitatea minimă găsită și se reia procesul. Acest proces continuă până când fertilitatea totală calculată este mai mică sau egală cu suma fertilităților tuturor zonelor.

În funcția "main", se apelează mai întâi funcția "validare" pentru a verifica corectitudinea datelor de intrare. Dacă datele sunt corecte, se apelează funcția "rezolvare" pentru a găsi fertilitatea maximă a unei parcele în care toate zonele au aceeași fertilitate. Rezultatul este apoi scris în fișierul "sao1.out".