2665 - Dreptunghi1 - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T11:57:45Z

Rezolvare

← Older revision		Revision as of 11:57, 29 December 2023
Line 42:		Line 42:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~calculeaza_aria_maxima~~(m, n, z, pozitii_0):		def verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):
	~~matrice~~ = [[1] * n ~~for _ in range(m~~)]		if not (1 <= m <= 10000 and 1 <= n <= 10000 and 1 <= z <= 10000):
			return False

	for lin, col in pozitii_0:		for lin, col in pozitii_0:
	~~matrice[~~lin][col~~] = 0~~		if not (0 <= lin < m and 0 <= col < n):
			return False

	~~def calculeaza_aria_linie~~(~~linie):~~		if not (0 <= aria_maxima <= m * n):
	~~stiva = []~~		return False
	~~aria_maxima =~~ 0
	~~coloana = 0~~

	~~while coloana~~ < n:
	~~if not stiva or matrice[linie][coloana] >~~= ~~matrice[linie][stiva[-1]]:~~
	~~stiva.append(coloana)~~
	~~coloana += 1~~
	~~else:~~
	~~top = stiva.pop()~~
	~~aria = matrice[linie][top] * (coloana if not stiva else coloana - stiva[-1] - 1)~~
	aria_maxima = ~~max(aria_maxima, aria)~~

	~~while stiva:~~
	~~top = stiva.pop()~~
	~~aria = matrice[linie][top]~~ * ~~(coloana if not stiva else coloana - stiva[-1] - 1)~~
	~~aria_maxima = max(aria_maxima, aria)~~

	~~return aria_maxima~~

	~~aria_maxima_totala = 0~~

	~~for linie in range(m~~):
	~~aria_maxima_totala = max(aria_maxima_totala, calculeaza_aria_linie(linie))~~

	return ~~aria_maxima_totala~~

			return True

	# Citire date de intrare		# Citire date de intrare
Line 87:		Line 65:
	# Scriere rezultat în fișier de ieșire		# Scriere rezultat în fișier de ieșire
	with open("dreptunghi1out.txt", "w") as f_out:		with open("dreptunghi1out.txt", "w") as f_out:
	f_out.write(f"{aria_maxima}\n")		if verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):
			f_out.write(f"{aria_maxima}\n")
			else:
			f_out.write("Datele introduse nu corespund restrictiilor impuse.\n")

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:22:34Z

Rezolvare

← Older revision		Revision as of 10:22, 27 December 2023
Line 42:		Line 42:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~arie_maxima_dreptunghi~~(~~matrix~~):		def calculeaza_aria_maxima(m, n, z, pozitii_0):
	~~def arie_histograma_maxima~~(~~inaltimi~~):		matrice = [[1] * n for _ in range(m)]
	~~stack = [~~]
	~~max_arie = 0~~
	~~i = 0~~

	while i < ~~len(inaltimi)~~:		for lin, col in pozitii_0:
	if not ~~stack~~ or ~~inaltimi~~[i] >= ~~inaltimi~~[~~stack~~[-1]]:		matrice[lin][col] = 0
	~~stack~~.append(i)
	i += 1		def calculeaza_aria_linie(linie):
			stiva = []
			aria_maxima = 0
			coloana = 0

			while coloana < n:
			if not stiva or matrice[linie][coloana] >= matrice[linie][stiva[-1]]:
			stiva.append(coloana)
			coloana += 1
	else:		else:
	top = ~~stack~~.pop()		top = stiva.pop()
	~~latime~~ = ~~i if not stack else i - stack~~[-1] ~~- 1~~		aria = matrice[linie][top] * (coloana if not stiva else coloana - stiva[-1] - 1)
	~~max_arie = max(max_arie, inaltimi~~[top] * ~~latime)~~		aria_maxima = max(aria_maxima, aria)

	~~while stack:~~
	~~top = stack.pop~~()
	~~latime = i~~ if not ~~stack~~ else i - ~~stack~~[-1] - 1
	~~max_arie~~ = max(~~max_arie~~, ~~inaltimi[top] * latime~~)

	~~return max_arie~~		while stiva:
			top = stiva.pop()
			aria = matrice[linie][top] * (coloana if not stiva else coloana - stiva[-1] - 1)
			aria_maxima = max(aria_maxima, aria)

	~~max_arie = 0~~		return aria_maxima
	~~histograma_rand = [0] * len(matrix[0])~~

	~~for rand in matrix:~~		aria_maxima_totala = 0
	~~for i in range(len(rand)):~~
	~~if rand[i] == 0:~~
	~~histograma_rand[i]~~ = 0
	~~else:~~
	~~histograma_rand[i] += 1~~

	~~max_arie~~ = max(~~max_arie~~, ~~arie_histograma_maxima~~(~~histograma_rand~~))		for linie in range(m):
			aria_maxima_totala = max(aria_maxima_totala, calculeaza_aria_linie(linie))

	return ~~max_arie~~		return aria_maxima_totala

	~~def main():~~
	~~with open("dreptunghi1.txt", "r") as fisier:~~
	~~m, n, z = map(int, fisier.readline().split())~~
	~~matrice = [[1] * n for _ in range(m)]~~

	~~for _ in range~~(z):		# Citire date de intrare
	~~linie~~, ~~coloana~~ = map(int, ~~fisier~~.readline().split())		with open("dreptunghi1in.txt", "r") as f:
	~~matrice~~[~~linie - 1][coloana - 1~~] ~~= 0~~		m, n, z = map(int, f.readline().split())
			pozitii_0 = [tuple(map(int, f.readline().split())) for _ in range(z)]

	~~rezultat~~ = ~~arie_maxima_dreptunghi~~(~~matrice~~)		# Calculare aria maxima
			aria_maxima = calculeaza_aria_maxima(m, n, z, pozitii_0)

	with open("~~dreptunghi1~~.txt", "w") as ~~fisier_out~~:		# Scriere rezultat în fișier de ieșire
	~~fisier_out~~.write(~~str(rezultat)~~)		with open("dreptunghi1out.txt", "w") as f_out:
			f_out.write(f"{aria_maxima}\n")

	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 10:21, 27 December 2023

2023-12-27T10:21:30Z

← Older revision		Revision as of 10:21, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== Cerinta ==

	Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 1?		Dată fiind o matrice dreptunghiulară cu elemente '''0 şi 1''', care este aria maximă a unui dreptunghi format numai din elemente egale cu 1?

	== Date de intrare ==		== Date de intrare ==

	Pe prima linie a fişierului ~~dreptunghi1~~.txt se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că elementul de la linia lin şi coloana col este 0. Restul elementelor matricei sunt considerate 1. Este posibil ca anumite perechi lin şi col să se repete.		Pe prima linie a fişierului '''dreptunghi1in.txt''' se vor găsi trei numere: numărul de linii, '''m''', al matricei, numărul de coloane, '''n''', precum şi numărul '''z''' al elementelor '''0''' din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că elementul de la linia lin şi coloana col este 0. Restul elementelor matricei sunt considerate 1. Este posibil ca anumite perechi lin şi col să se repete.

	== Date de iesire ==		== Date de iesire ==

	Fişierul ~~dreptunghi1~~.txt va conţine un singur număr, aria celui mai mare dreptunghi plin numai cu 1.		Fişierul '''dreptunghi1out.txt''' va conţine un singur număr, aria celui mai mare dreptunghi plin numai cu 1.

	== Restrictii si precizari ==		== Restrictii si precizari ==

	*1 ≤ m, n, z ≤ 10.000;		*'''1 &les; m, n, z &les; 10.000''';
	*Perechile lin şi col sunt coordonate corecte în matrice, nu neapărat unice.		*Perechile lin şi col sunt coordonate corecte în matrice, nu neapărat unice.

Line 22:		Line 22:

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;dreptunghi1in.txt
	:6 6 3		:6 6 3
	:4 1		:4 1
	:4 5		:4 5
	:3 3		:3 3
	;~~Iesire~~		;dreptunghi1out.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:12		:12

	== Exemplul 2 ==		== Exemplul 2 ==
	;~~Intrare~~		;dreptunghi1in.txt
	:1 2		:1 2
	:0 0		:0 0
	:-1 -2 -3		:-1 -2 -3
	~~;Iesire~~
	;Datele introduse nu corespund restrictiilor impuse		:Datele introduse nu corespund restrictiilor impuse

Mesarosdenisa: Pagină nouă: == Cerinta == Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 1? == Date de intrare == Pe prima linie a fişierului dreptunghi1.txt se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că...

2023-12-12T15:52:07Z

Pagină nouă: == Cerinta == Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 1? == Date de intrare == Pe prima linie a fişierului dreptunghi1.txt se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că...

New page

== Cerinta ==

Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 1?

== Date de intrare ==

Pe prima linie a fişierului dreptunghi1.txt se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cate o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că elementul de la linia lin şi coloana col este 0. Restul elementelor matricei sunt considerate 1. Este posibil ca anumite perechi lin şi col să se repete.

== Date de iesire ==

Fişierul dreptunghi1.txt va conţine un singur număr, aria celui mai mare dreptunghi plin numai cu 1.

== Restrictii si precizari ==

*1 ≤ m, n, z ≤ 10.000;
*Perechile lin şi col sunt coordonate corecte în matrice, nu neapărat unice.

== Punctaje partiale ==

*Pentru 20% din teste: 1 ≤ m, n ≤ 30;
*Pentru 40% din teste: 1 ≤ m, n ≤ 100.

== Exemplul 1 ==
;Intrare
:6 6 3
:4 1
:4 5
:3 3
;Iesire
;Datele introduse corespund restrictiilor impuse
:12

== Exemplul 2 ==
;Intrare
:1 2
:0 0
:-1 -2 -3
;Iesire
;Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def arie_maxima_dreptunghi(matrix):
def arie_histograma_maxima(inaltimi):
stack = []
max_arie = 0
i = 0

while i < len(inaltimi):
if not stack or inaltimi[i] >= inaltimi[stack[-1]]:
stack.append(i)
i += 1
else:
top = stack.pop()
latime = i if not stack else i - stack[-1] - 1
max_arie = max(max_arie, inaltimi[top] * latime)

while stack:
top = stack.pop()
latime = i if not stack else i - stack[-1] - 1
max_arie = max(max_arie, inaltimi[top] * latime)

return max_arie

max_arie = 0
histograma_rand = [0] * len(matrix[0])

for rand in matrix:
for i in range(len(rand)):
if rand[i] == 0:
histograma_rand[i] = 0
else:
histograma_rand[i] += 1

max_arie = max(max_arie, arie_histograma_maxima(histograma_rand))

return max_arie

def main():
with open("dreptunghi1.txt", "r") as fisier:
m, n, z = map(int, fisier.readline().split())
matrice = [[1] * n for _ in range(m)]

for _ in range(z):
linie, coloana = map(int, fisier.readline().split())
matrice[linie - 1][coloana - 1] = 0

rezultat = arie_maxima_dreptunghi(matrice)

with open("dreptunghi1.txt", "w") as fisier_out:
fisier_out.write(str(rezultat))

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==

Matricea este:
;111111
;111111
:110111
:011101
:111111
:111111
Cel mai mare dreptunghi are arie 12.