4081 - alpinistii - Revision history

Catalin Moje at 20:44, 14 May 2023

2023-05-14T20:44:34Z

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

	1 ≤ n ≤ 200		*1 ≤ n ≤ 200
	1 ≤ m ≤ 200		*1 ≤ m ≤ 200
	în matrice sunt doar valori de 0 și 1		*în matrice sunt doar valori de 0 și 1
	Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, iar pentru cerința 2 se acordă 60 puncte.		*Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, iar pentru cerința 2 se acordă 60 puncte.

	==Exemplu==		==Exemplu==
	===Exemplu1===		===Exemplu1===
			:Intrare:
	alpinisti.in		;alpinisti.in
	~~<syntaxhighlight lang="python">~~		;1 7 8
	1 7 8		;1 1 1 1 1 1 1 1
	1 1 1 1 1 1 1 1		;1 0 0 1 1 1 1 0
	1 0 0 1 1 1 1 0		;1 1 0 1 0 0 0 1
	1 1 0 1 0 0 0 1		;1 1 0 1 0 0 1 1
	1 1 0 1 0 0 1 1		;0 1 1 0 0 0 0 1
	0 1 1 0 0 0 0 1		;0 0 1 0 0 0 0 1
	0 0 1 0 0 0 0 1		;1 0 0 1 1 1 1 1
	1 0 0 1 1 1 1 1
	~~</syntaxhighlight>~~		:Iesire:
			;alpinisti.out
			;13

	~~alpinisti.out~~
	~~<syntaxhighlight lang="python">~~
	13
	~~</syntaxhighlight>~~

	===Exemplu2===		===Exemplu2===
	alpinisti.in		:Intrare:
	~~<syntaxhighlight lang="python">~~		;alpinisti.in
	2 7 8		;2 7 8
	1 1 1 1 1 1 1 1		;1 1 1 1 1 1 1 1
	1 0 0 1 1 1 1 0		;1 0 0 1 1 1 1 0
	1 1 0 1 0 0 0 1		;1 1 0 1 0 0 0 1
	1 1 0 1 0 0 1 1		;1 1 0 1 0 0 1 1
	0 1 1 0 0 0 0 1		;0 1 1 0 0 0 0 1
	0 0 1 0 0 0 0 1		;0 0 1 0 0 0 0 1
	1 0 0 1 1 1 1 1		;1 0 0 1 1 1 1 1
	~~</syntaxhighlight>~~		:Iesire:
			;alpinisti.out
	alpinisti.out		;9
	~~<syntaxhighlight lang="python">~~
	9
	~~</syntaxhighlight>~~

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

	def validare(n, m, matrice):		def validare(n, m, matrice):
Line 148:		Line 143:
	Acest cod este o soluție pentru problema "Alpiniști" și se împarte în trei funcții:		Acest cod este o soluție pentru problema "Alpiniști" și se împarte în trei funcții:

	Funcția validare(n, m, matrice) are rolul de a verifica dacă datele de intrare sunt valide. În cazul de față, se verifică dacă n și m se află în intervalul [1, 200] și dacă matricea matrice are dimensiunea corespunzătoare și conține doar caracterele '0' și '1'. Această verificare este importantă pentru a ne asigura că programul primește date valide și poate produce un rezultat corect.		#1 Funcția validare(n, m, matrice) are rolul de a verifica dacă datele de intrare sunt valide. În cazul de față, se verifică dacă n și m se află în intervalul [1, 200] și dacă matricea matrice are dimensiunea corespunzătoare și conține doar caracterele '0' și '1'. Această verificare este importantă pentru a ne asigura că programul primește date valide și poate produce un rezultat corect.

	Funcția rezolvare1(n, m, matrice) calculează numărul maxim de spații sigure care pot fi găsite în matricea dată. Se parcurge fiecare element al matricei și se verifică dacă acesta este un spațiu sigur ('0'). Dacă este, se inițializează un contor la 0 și se adaugă poziția elementului într-o coadă. Apoi, se parcurge coada și se verifică dacă poziția curentă este un spațiu sigur. Dacă da, se incrementează contorul, se marchează spațiul ca fiind vizitat și se adaugă în coadă toți vecinii săi care sunt spații sigure și nu au fost deja vizitați. Acest proces continuă până când coada este goală și se înregistrează numărul maxim de spații sigure găsite până în acel moment. Această metodă se bazează pe algoritmul de căutare în lățime (BFS) și ne permite să găsim numărul maxim de spații sigure în matricea dată.		#2 Funcția rezolvare1(n, m, matrice) calculează numărul maxim de spații sigure care pot fi găsite în matricea dată. Se parcurge fiecare element al matricei și se verifică dacă acesta este un spațiu sigur ('0'). Dacă este, se inițializează un contor la 0 și se adaugă poziția elementului într-o coadă. Apoi, se parcurge coada și se verifică dacă poziția curentă este un spațiu sigur. Dacă da, se incrementează contorul, se marchează spațiul ca fiind vizitat și se adaugă în coadă toți vecinii săi care sunt spații sigure și nu au fost deja vizitați. Acest proces continuă până când coada este goală și se înregistrează numărul maxim de spații sigure găsite până în acel moment. Această metodă se bazează pe algoritmul de căutare în lățime (BFS) și ne permite să găsim numărul maxim de spații sigure în matricea dată.

	Funcția rezolvare2(n, m, matrice) calculează aria maximă a unui dreptunghi format doar din spații sigure din matricea dată. În această funcție se folosește o metodă de programare dinamică. Se construiește o matrice dp cu aceleași dimensiuni ca și matricea matrice, inițializată cu zero. Pentru fiecare element din matricea matrice care este un spațiu sigur ('0'), se calculează lățimea maximă și înălțimea maximă a unui dreptunghi de spații sigure care include acel element, iar apoi se calculează aria maximă a dreptunghiului care conține acel element. Această metodă se bazează pe observația că orice dreptunghi format doar din spații sigure trebuie să includă un element din matricea matrice și că putem folosi matricea dp pentru a evita să re-calculăm dreptunghiuri în mod repetat.		#3 Funcția rezolvare2(n, m, matrice) calculează aria maximă a unui dreptunghi format doar din spații sigure din matricea dată. În această funcție se folosește o metodă de programare dinamică. Se construiește o matrice dp cu aceleași dimensiuni ca și matricea matrice, inițializată cu zero. Pentru fiecare element din matricea matrice care este un spațiu sigur ('0'), se calculează lățimea maximă și înălțimea maximă a unui dreptunghi de spații sigure care include acel element, iar apoi se calculează aria maximă a dreptunghiului care conține acel element. Această metodă se bazează pe observația că orice dreptunghi format doar din spații sigure trebuie să includă un element din matricea matrice și că putem folosi matricea dp pentru a evita să re-calculăm dreptunghiuri în mod repetat.

	În if __name__ == '__main__': se deschide fișierul de intrare 'alpinisti.in' și se citesc datele de intrare. Apoi, în funcția main(), se verifică dacă datele de intrare sunt valide folosind funcția validare(). Dacă acestea sunt valide, se calculează numărul maxim de spații sigure și aria maximă a unui dreptunghi format doar din spații sigure, folosind funcțiile rezolvare1() și rezolvare2(). Aceste valori sunt apoi scrise în fișierul de ieșire 'alpinisti.out'.		#4 În if __name__ == '__main__': se deschide fișierul de intrare 'alpinisti.in' și se citesc datele de intrare. Apoi, în funcția main(), se verifică dacă datele de intrare sunt valide folosind funcția validare(). Dacă acestea sunt valide, se calculează numărul maxim de spații sigure și aria maximă a unui dreptunghi format doar din spații sigure, folosind funcțiile rezolvare1() și rezolvare2(). Aceste valori sunt apoi scrise în fișierul de ieșire 'alpinisti.out'.

Catalin Moje: Pagină nouă: ==Enunț== Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup. Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvam...

2023-04-29T23:22:25Z

Pagină nouă: ==Enunț== Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup. Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvam...

New page

==Enunț==
Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup. Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvamontiști. Informaticienii reușesc să analizeze spațiile sigure ale versantului și să reprezinte versantul cu ajutorul unei matrice binare. Fiecare spațiu sigur este codificat cu 0, iar valorile de 1 reprezintă spațiile blocate.
Ei vă cer ajutorul pentru a reuși să-i salveze pe alpiniști.

==Cerința==
Cunoscând matricea binară ce codifică versantul, determinați:
1) Numărul maxim de spații sigure ce pot forma o zonă-adăpost de pe versant
2) Numărul maxim de spații sigure dintr-o zonă-adăpost dreptunghiulară corespunzătoare unui dreptunghi format doar din valori de 0 din matricea dată.

==Date de intrare==
Fișierul de intrare alpinistii.in conține pe prima linie trei numere naturale: c, n și m, separate prin câte un spațiu, c reprezentând numărul cerinței ce urmează a fi rezolvată (1 sau 2), n reprezentând numărul de linii ale matricei, iar m numărul de coloane. Fiecare dintre următoarele n linii conține câte m cifre de 0 și 1, separate prin câte un spațiu, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire alpinistii.out va conține pe prima linie un număr natural reprezentând răspunsul la cerința care se rezolvă.

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

1 ≤ n ≤ 200
1 ≤ m ≤ 200
în matrice sunt doar valori de 0 și 1
Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, iar pentru cerința 2 se acordă 60 puncte.

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

alpinisti.in
<syntaxhighlight lang="python">
1 7 8
1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 0
1 1 0 1 0 0 0 1
1 1 0 1 0 0 1 1
0 1 1 0 0 0 0 1
0 0 1 0 0 0 0 1
1 0 0 1 1 1 1 1
</syntaxhighlight>

alpinisti.out
<syntaxhighlight lang="python">
13
</syntaxhighlight>

===Exemplu2===
alpinisti.in
<syntaxhighlight lang="python">
2 7 8
1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 0
1 1 0 1 0 0 0 1
1 1 0 1 0 0 1 1
0 1 1 0 0 0 0 1
0 0 1 0 0 0 0 1
1 0 0 1 1 1 1 1
</syntaxhighlight>

alpinisti.out
<syntaxhighlight lang="python">
9
</syntaxhighlight>

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

def validare(n, m, matrice):
if n < 1 or n > 200:
return False
if m < 1 or m > 200:
return False
for i in range(n):
if len(matrice[i]) != m:
return False
for j in range(m):
if matrice[i][j] != '0' and matrice[i][j] != '1':
return False
return True

def rezolvare1(n, m, matrice):
max_spatii = 0
for i in range(n):
for j in range(m):
if matrice[i][j] == '0':
count = 0
queue = [(i, j)]
while queue:
x, y = queue.pop(0)
if matrice[x][y] == '0':
count += 1
matrice[x][y] = '1'
if x > 0 and matrice[x-1][y] == '0':
queue.append((x-1, y))
if x < n-1 and matrice[x+1][y] == '0':
queue.append((x+1, y))
if y > 0 and matrice[x][y-1] == '0':
queue.append((x, y-1))
if y < m-1 and matrice[x][y+1] == '0':
queue.append((x, y+1))
max_spatii = max(max_spatii, count)
return max_spatii

def rezolvare2(n, m, matrice):
# initializam matricea dp cu 0-uri
dp = [[0] * m for _ in range(n)]

# calculam lățimea și înălțimea maximă a unui dreptunghi de spații sigure care include fiecare element
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
if matrice[i][j] == '0':
w = dp[i][j+1] + 1 if j < m-1 else 1
h = dp[i+1][j] + 1 if i < n-1 else 1
dp[i][j] = min(w, h)

# calculam aria maximă a unui dreptunghi format doar din spații sigure din matrice
max_area = 0
for i in range(n):
for j in range(m):
if matrice[i][j] == '0':
area = dp[i][j] * dp[i][j]
max_area = max(max_area, area)

return max_area

if __name__ == '__main__':
with open('alpinisti.in', 'r') as f:
cerinta, n, m = map(int, f.readline().strip().split())
matrice = [list(f.readline().strip().split()) for _ in range(n)]

if cerinta == 1:
if not validare(n, m, matrice):
with open('alpinisti.out', 'w') as f:
f.write('Date de intrare invalide')
else:
max_spatii = rezolvare1(n, m, matrice)
with open('alpinisti.out', 'w') as f:
f.write(str(max_spatii))

elif cerinta == 2:
max_spatii = rezolvare2(n, m,matrice)
with open('alpinisti.out', 'w') as f:
f.write(str(max_spatii))

</syntaxhighlight>

==Explicații ==
Acest cod este o soluție pentru problema "Alpiniști" și se împarte în trei funcții:

Funcția validare(n, m, matrice) are rolul de a verifica dacă datele de intrare sunt valide. În cazul de față, se verifică dacă n și m se află în intervalul [1, 200] și dacă matricea matrice are dimensiunea corespunzătoare și conține doar caracterele '0' și '1'. Această verificare este importantă pentru a ne asigura că programul primește date valide și poate produce un rezultat corect.

Funcția rezolvare1(n, m, matrice) calculează numărul maxim de spații sigure care pot fi găsite în matricea dată. Se parcurge fiecare element al matricei și se verifică dacă acesta este un spațiu sigur ('0'). Dacă este, se inițializează un contor la 0 și se adaugă poziția elementului într-o coadă. Apoi, se parcurge coada și se verifică dacă poziția curentă este un spațiu sigur. Dacă da, se incrementează contorul, se marchează spațiul ca fiind vizitat și se adaugă în coadă toți vecinii săi care sunt spații sigure și nu au fost deja vizitați. Acest proces continuă până când coada este goală și se înregistrează numărul maxim de spații sigure găsite până în acel moment. Această metodă se bazează pe algoritmul de căutare în lățime (BFS) și ne permite să găsim numărul maxim de spații sigure în matricea dată.

Funcția rezolvare2(n, m, matrice) calculează aria maximă a unui dreptunghi format doar din spații sigure din matricea dată. În această funcție se folosește o metodă de programare dinamică. Se construiește o matrice dp cu aceleași dimensiuni ca și matricea matrice, inițializată cu zero. Pentru fiecare element din matricea matrice care este un spațiu sigur ('0'), se calculează lățimea maximă și înălțimea maximă a unui dreptunghi de spații sigure care include acel element, iar apoi se calculează aria maximă a dreptunghiului care conține acel element. Această metodă se bazează pe observația că orice dreptunghi format doar din spații sigure trebuie să includă un element din matricea matrice și că putem folosi matricea dp pentru a evita să re-calculăm dreptunghiuri în mod repetat.

În if __name__ == '__main__': se deschide fișierul de intrare 'alpinisti.in' și se citesc datele de intrare. Apoi, în funcția main(), se verifică dacă datele de intrare sunt valide folosind funcția validare(). Dacă acestea sunt valide, se calculează numărul maxim de spații sigure și aria maximă a unui dreptunghi format doar din spații sigure, folosind funcțiile rezolvare1() și rezolvare2(). Aceste valori sunt apoi scrise în fișierul de ieșire 'alpinisti.out'.