2741 - SAO1 - Revision history

Catalin Moje at 20:48, 14 May 2023

2023-05-14T20:48:59Z

← Older revision		Revision as of 20:48, 14 May 2023
Line 16:		Line 16:
	*fertilitatea totală se va încadra pe tipul de date long long.		*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).		*nu există sol infertil (a cărui fertilitate să fie mai mică sau egală cu 0).
	acesta este “bad ending”-ul problemei SAO		*acesta este “bad ending”-ul problemei SAO

	==Exemplu==		==Exemplu==

Catalin Moje at 20:48, 14 May 2023

2023-05-14T20:48:31Z

← Older revision		Revision as of 20:48, 14 May 2023
Line 13:		Line 13:
	==Restricții și precizări==		==Restricții și precizări==

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

	==Exemplu==		==Exemplu==
	===Exemplu1===		===Exemplu1===
			:Intrare:
	SAO1.in		;SAO1.in
	~~<syntaxhighlight lang="python">~~		;4 4
	4 4		;1 1 1 3
	1 1 1 3		;1 1 1 3
	1 1 1 3		;1 1 1 3
	1 1 1 3		;3 3 3 3
	3 3 3 3		:Iesire:
	~~</syntaxhighlight>~~		;SAO1.out
			;21
	SAO1.out
	~~<syntaxhighlight lang="python">~~
	21
	~~</syntaxhighlight>~~

	===Exemplu2===		===Exemplu2===
	SAO1.in		:Intrare:
	~~<syntaxhighlight lang="python">~~		;SAO1.in
	4 4		;4 4
	3 5 1 3		;3 5 1 3
	1 5 5 3		;1 5 5 3
	5 5 5 3		;5 5 5 3
	3 3 3 3		;3 3 3 3
	~~</syntaxhighlight>~~		:Iesire:
			;SAO1.out
	SAO1.out		;30
	~~<syntaxhighlight lang="python">~~
	30
	~~</syntaxhighlight>~~

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python" line="1">

	def validare(n, m, matrice):		def validare(n, m, matrice):
Line 115:		Line 108:

	==Explicații ==		==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ă.		#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ă.

	Î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.		#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.

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

Catalin Moje: Pagină nouă: ==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 fertilit...

2023-05-04T18:50:48Z

Pagină nouă: ==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 fertilit...

New page

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