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".