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
- Intrare:
- SAO1.in
- 4 4
- 1 1 1 3
- 1 1 1 3
- 1 1 1 3
- 3 3 3 3
- Iesire:
- SAO1.out
- 21
Exemplu2
- Intrare:
- SAO1.in
- 4 4
- 3 5 1 3
- 1 5 5 3
- 5 5 5 3
- 3 3 3 3
- Iesire:
- SAO1.out
- 30
Rezolvare
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()
Explicații
- 1 Codul î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ă.
- 2 Î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.
- 3 Î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".
