Catalin Moje at 20:57, 14 May 2023

2023-05-14T20:57:08Z

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

	≤ n , m ≤ 100		*≤ n , m ≤ 100

	==Exemplu==		==Exemplu==
	===Exemplu1===		===Exemplu1===
			:Intrare:
	croco1.in		;croco1.in
	~~<syntaxhighlight lang="python">~~		;3 5
	3 5		;0 0 0 1 0
	0 0 0 1 0		;0 0 1 0 0
	0 0 1 0 0		;1 0 0 1 0
	1 0 0 1 0		:Iesire:
	~~</syntaxhighlight>~~		;croco1.out
			;7 4
	croco1.out
	~~<syntaxhighlight lang="python">~~
	7 4
	~~</syntaxhighlight>~~


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

	def valideaza_matrice(matrice):		def valideaza_matrice(matrice):
Line 87:		Line 83:

	==Explicații ==		==Explicații ==
	Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1. Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice.		#1 Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1.
			#2 Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice.

	Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire.		#3 Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire.

Catalin Moje: Pagină nouă: ==Cerința== Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă. Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare. Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel...

2023-05-04T19:49:40Z

Pagină nouă: ==Cerința== Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă. Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare. Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel...

New page

==Cerința==
Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă.

Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare.

Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel încât numărul de crocodili să fie cât mai mare.

==Date de intrare==
ișierul de intrare croco1.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau 1, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire croco1.out va conține pe prima linie numerele C E, reprezentând numărul de crocodili, respectiv numărul de elefanți care pot fi plasați în condițiile precizate, astfel încât numărul de crocodili să fie cât mai mare.

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

≤ n , m ≤ 100

==Exemplu==
===Exemplu1===

croco1.in
<syntaxhighlight lang="python">
3 5
0 0 0 1 0
0 0 1 0 0
1 0 0 1 0
</syntaxhighlight>

croco1.out
<syntaxhighlight lang="python">
7 4
</syntaxhighlight>

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

def valideaza_matrice(matrice):
for linie in matrice:
if len(linie) != len(matrice[0]):
return False
for element in linie:
if element != 0 and element != 1:
return False
return True

def rezolva_crocodili(matrice):
nr_crocodili = 0
nr_elefanti = 0
directii = [(0, -1), (-1, 0), (0, 1), (1, 0)]
for i in range(len(matrice)):
for j in range(len(matrice[0])):
if matrice[i][j] == 0:
poate_fi_croc = True
for dx, dy in directii:
x, y = i + dx, j + dy
if 0 <= x < len(matrice) and 0 <= y < len(matrice[0]):
if matrice[x][y] == 2:
poate_fi_croc = False
break
if poate_fi_croc:
matrice[i][j] = 2
nr_crocodili += 1
nr_elefanti = sum(linie.count(0) for linie in matrice)
return nr_crocodili, nr_elefanti

def main():
with open("croco1.in") as f:
n, m = map(int, f.readline().split())
matrice = [list(map(int, f.readline().split())) for _ in range(n)]
if not valideaza_matrice(matrice):
print("Matricea data nu este valida.")
return
nr_crocodili, nr_elefanti = rezolva_crocodili(matrice)
with open("croco1.out", "w") as f:
f.write(f"{nr_crocodili} {nr_elefanti}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicații ==
Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1. Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice.

Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire.

0844 - Croco1 - Revision history

Catalin Moje at 20:57, 14 May 2023