1973 - Hambar2 - Revision history

Cata at 14:29, 14 May 2023

2023-05-14T14:29:31Z

← Older revision		Revision as of 14:29, 14 May 2023
Line 22:		Line 22:
	: 5 1		: 5 1
	: 5 5		: 5 5
	:hambar2.out		; hambar2.out
	: 12		: 12
	; Consolă		; Consolă

Cata: /* Exemplu */

2023-05-03T06:36:20Z

Exemplu

← Older revision		Revision as of 06:36, 3 May 2023
Line 25:		Line 25:
	: 12		: 12
	; Consolă		; Consolă
	: ~~Valid input~~		: Input valid
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">

Cata at 06:28, 3 May 2023

2023-05-03T06:28:33Z

← Older revision		Revision as of 06:28, 3 May 2023
Line 10:		Line 10:
	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.		Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.
	În consolă se va afișa un mesaj de validare a datelor.		În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau instrucțiuni cu privire la n sau m).
	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ N, M ≤ 1000		* 1 ≤ N, M ≤ 1000
Line 94:		Line 94:
	def validate_input(n, m):		def validate_input(n, m):
	if not 1 <= n <= 1000:		if not 1 <= n <= 1000:
	raise ValueError("n ~~must be between~~ 1 ~~and~~ 1000")		raise ValueError("n trebuie să fie între 1 și 1000")
	return 0		return 0
	if not 1 <= m <= 1000:		if not 1 <= m <= 1000:
	raise ValueError("m ~~must be between~~ 1 ~~and~~ 1000")		raise ValueError("m trebuie să fie între 1 și 1000")
	return 0		return 0
	return 1		return 1

	~~def main()~~:		if __name__ == '__main__':
	with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:		with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
	n, m = map(int, fin.readline().split())		n, m = map(int, fin.readline().split())
	if validate_input(n, m):		if validate_input(n, m):
	print("~~Valid input~~")		print("Input valid")

	mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]		mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
Line 114:		Line 114:
	fout.write(str(calculate_max_rect(n, mat)))		fout.write(str(calculate_max_rect(n, mat)))

	~~if __name__ == '__main__':~~
	~~main()~~
	</syntaxhighlight>		</syntaxhighlight>

	==Explicație==		==Explicație==
	Acest cod ~~este~~ o ~~implementare Python a algoritmului~~ de ~~determinare~~ a ~~celui~~ mai mare dreptunghi ~~înmatriculabil~~ într-o matrice dată~~. Programul primește un fișier~~ de ~~intrare 'hambar2~~.~~in' care~~ conține dimensiunile matricei (n, m) și pozițiile elementelor din matrice care au valoarea True. Aceste elemente reprezintă pătrate ocupate în matrice. Scopul programului este să găsească cel mai mare dreptunghi neocupat din matrice și să returneze aria acestuia.		Acest cod implementează o soluție pentru problema de a găsi cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe într-o matrice dată de dimensiunea n x n. Mai precis, codul conține următoarele funcții:

	~~Algoritmul funcționează astfel:~~		- Funcția "clear" golește conținutul unei stive date ca argument;
			- Funcția "calculate_histogram" calculează histograma pentru matricea dată și returnează o listă de dimensiune n+1, unde primul element este 0 și următoarele elemente reprezintă înălțimea coloanelor corespunzătoare din matrice;
			- Funcțiile "calculate_left_boundary" și "calculate_right_boundary" calculează limitele stângi, respectiv drepte ale dreptunghiurilor care conțin fiecare coloană din matricea dată și care au înălțimile date de histograma calculată anterior. Acestea returnează două liste de dimensiune n+1, unde primul și ultimul element sunt 0, iar restul elementelor reprezintă limitele stângi sau drepte corespunzătoare;
			- Funcția "calculate_max_rect" calculează cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe în matricea dată, folosind funcțiile "calculate_histogram", "calculate_left_boundary" și "calculate_right_boundary";
			- Funcția "validate_input" verifică dacă valorile n și m sunt în intervalul [1, 1000] și generează o excepție în caz contrar.

	* Se calculează histograma pentru ~~fiecare linie a~~ matricei~~. Histograma reprezintă~~ numărul de ~~pătrate goale consecutive~~ din ~~fiecare linie~~.		În secțiunea "if __name__ == '__main__':" se deschide fișierul "hambar2.in" pentru citire și fișierul "hambar2.out" pentru scriere, se citește dimensiunea matricei și numărul de elemente albe din aceasta și se verifică dacă valorile introduse sunt valide. Dacă sunt, se construiește matricea folosind elementele citite și se apelează funcția "calculate_max_rect" pentru a calcula cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe. Rezultatul este scris în fișierul "hambar2.out".
	* Se determină limitele stângi și drepte ale fiecărei coloane a matricei, folosind ~~stack-uri~~ și ~~histograma calculată anterior.~~
	* Se calculează aria fiecărui dreptunghi care are baza în fiecare coloană și înălțimea dată de histograma corespunzătoare.
	* Se alege cel mai mare dreptunghi ~~dintre cele calculate~~.
	~~În final, programul scrie aria dreptunghiului găsit~~ în fișierul 'hambar2.out'.

Cata at 07:35, 28 April 2023

2023-04-28T07:35:25Z

← Older revision		Revision as of 07:35, 28 April 2023
Line 10:		Line 10:
	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.		Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.
			În consolă se va afișa un mesaj de validare a datelor.
	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ N, M ≤ 1000		* 1 ≤ N, M ≤ 1000
	* Nu se vor afla 2 sau mai mulți pomi în același loc.		* Nu se vor afla 2 sau mai mulți pomi în același loc.
	==Exemplu==		==Exemplu==
	hambar2.in		; hambar2.in
			: 5 5
	5 5		: 1 3
	1 3		: 2 1
	2 1		: 2 5
	2 5		: 5 1
	5 1		: 5 5
	5 5		:hambar2.out
	hambar2.out		: 12
			; Consolă
	12		: Valid input

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
Line 96:		Line 95:
	if not 1 <= n <= 1000:		if not 1 <= n <= 1000:
	raise ValueError("n must be between 1 and 1000")		raise ValueError("n must be between 1 and 1000")
			return 0
	if not 1 <= m <= 1000:		if not 1 <= m <= 1000:
	raise ValueError("m must be between 1 and 1000")		raise ValueError("m must be between 1 and 1000")
			return 0
			return 1

	def main():		def main():
	with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:		with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
	n, m = map(int, fin.readline().split())		n, m = map(int, fin.readline().split())
	validate_input(n, m)		if validate_input(n, m):
			print("Valid input")

	mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]		mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
Line 113:		Line 116:
	if __name__ == '__main__':		if __name__ == '__main__':
	main()		main()

	</syntaxhighlight>		</syntaxhighlight>

Cata: Pagină nouă: ==Enunț== Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de ar...

2023-04-20T15:52:58Z

Pagină nouă: ==Enunț== Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de ar...

New page

==Enunț==
Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

==Cerința==
Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

==Date de intrare==
Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

==Date de ieșire==
Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.

==Restricții și precizări==
* 1 ≤ N, M ≤ 1000
* Nu se vor afla 2 sau mai mulți pomi în același loc.
==Exemplu==
hambar2.in

5 5
1 3
2 1
2 5
5 1
5 5
hambar2.out

12

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

def clear(stiva):
while stiva:
stiva.pop()

def calculate_histogram(n, mat):
h = [0] * (n + 1)

for i in range(1, n+1):
for j in range(1, n+1):
if not mat[i][j]:
h[j] += 1
else:
h[j] = 0

return h

def calculate_left_boundary(n, h):
st = [0] * (n + 1)
stiva = []

for j in range(1, n+1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
st[j] = 0
else:
st[j] = stiva[-1]

stiva.append(j)

return st

def calculate_right_boundary(n, h):
dr = [0] * (n + 1)
stiva = []

for j in range(n, 0, -1):
while stiva and h[stiva[-1]] >= h[j]:
stiva.pop()

if not stiva:
dr[j] = n+1
else:
dr[j] = stiva[-1]

stiva.append(j)

return dr

def calculate_max_rect(n, mat):
arieMAX = 0

h = calculate_histogram(n, mat)
st = calculate_left_boundary(n, h)
dr = calculate_right_boundary(n, h)

for j in range(1, n+1):
arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

return arieMAX

def validate_input(n, m):
if not 1 <= n <= 1000:
raise ValueError("n must be between 1 and 1000")
if not 1 <= m <= 1000:
raise ValueError("m must be between 1 and 1000")

def main():
with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
n, m = map(int, fin.readline().split())
validate_input(n, m)

mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
for _ in range(m):
x, y = map(int, fin.readline().split())
mat[x][y] = True

fout.write(str(calculate_max_rect(n, mat)))

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicație==
Acest cod este o implementare Python a algoritmului de determinare a celui mai mare dreptunghi înmatriculabil într-o matrice dată. Programul primește un fișier de intrare 'hambar2.in' care conține dimensiunile matricei (n, m) și pozițiile elementelor din matrice care au valoarea True. Aceste elemente reprezintă pătrate ocupate în matrice. Scopul programului este să găsească cel mai mare dreptunghi neocupat din matrice și să returneze aria acestuia.

Algoritmul funcționează astfel:

* Se calculează histograma pentru fiecare linie a matricei. Histograma reprezintă numărul de pătrate goale consecutive din fiecare linie.
* Se determină limitele stângi și drepte ale fiecărei coloane a matricei, folosind stack-uri și histograma calculată anterior.
* Se calculează aria fiecărui dreptunghi care are baza în fiecare coloană și înălțimea dată de histograma corespunzătoare.
* Se alege cel mai mare dreptunghi dintre cele calculate.
În final, programul scrie aria dreptunghiului găsit în fișierul 'hambar2.out'.