Zmicala Narcis: Pagină nouă: == Enunț == Gigel are o grădina sub forma unei matrice binare de ordin '''N''', unde 0 reprezintă teren liber, '''1''' reprezintă pomi. El dorește să construiască un hambar pe dreptunghiul de arie maximă format doar din '''0'''. == Cerința == Ajutați-l pe Gigel să găsească dreptunghiul de arie maximă format doar din '''0'''. == Date de intrare == Fișierul de intrare '''hambarin.txt''' conține pe prima linie numerele '''N''' și '''M''', reprezentând dimensinu...

2024-01-02T18:06:02Z

Pagină nouă: == Enunț == Gigel are o grădina sub forma unei matrice binare de ordin '''N''', unde 0 reprezintă teren liber, '''1''' reprezintă pomi. El dorește să construiască un hambar pe dreptunghiul de arie maximă format doar din '''0'''. == Cerința == Ajutați-l pe Gigel să găsească dreptunghiul de arie maximă format doar din '''0'''. == Date de intrare == Fișierul de intrare '''hambarin.txt''' conține pe prima linie numerele '''N''' și '''M''', reprezentând dimensinu...

New page

== Enunț ==
Gigel are o grădina sub forma unei matrice binare de ordin '''N''', unde 0 reprezintă teren liber, '''1''' reprezintă pomi. El dorește să construiască un hambar pe dreptunghiul de arie maximă format doar din '''0'''.
== Cerința ==
Ajutați-l pe Gigel să găsească dreptunghiul de arie maximă format doar din '''0'''.
== Date de intrare ==
Fișierul de intrare '''hambarin.txt''' 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 perechi 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 '''hambarout.txt''' va conține pe prima linie numărul '''S''', reprezentând aria maximă a unei suprafețe dreptunghiulare ce nu conține '''1'''.
== Restricții și precizări ==
* '''1 ≤ N, M ≤ 1000'''
* Nu se vor afla '''2''' sau mai mulți pomi în același loc.
== Exemplul 1 ==
; hambarin.txt
: 5 5
: 1 3
: 2 1
: 2 5
: 5 1
: 5 5
; hambarout.txt
: Datele introduse corespund restricțiilor impuse.
: 12
== Exemplul 2 ==
; hambarin.txt
: 5 5
: 1 3
: 2 1
: 2 5
: 5 1
: 5 1000
; hambarout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 1972 - Hambar
def validare(dim_n1, dim_m1, lista_pomi1): # functia de validare a datelor de intrare
if dim_n1 < 1 or dim_n1 > 1000 or dim_m1 < 1 or dim_m1 > 1000:
raise ValueError

for pom in lista_pomi1:
if pom[0] < 1 or pom[0] > dim_n1 or pom[1] < 1 or pom[1] > dim_n1:
raise ValueError

fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def arie_maxima(dim_n1, lista_pomi1): # functia de rezolvare
matrice = [[0] * dim_n1 for _ in range(dim_n1)]
for pom in lista_pomi1:
matrice[pom[0]-1][pom[1]-1] = 1

dp = [[0] * dim_n1 for _ in range(dim_n1)]
max_area = 0

for i in range(dim_n1):
for j in range(dim_n1):
if matrice[i][j] == 0:
dp[i][j] = dp[i-1][j] + 1 if i > 0 else 1

for i in range(dim_n1):
for j in range(dim_n1):
width = dp[i][j]
for k in range(i, -1, -1):
width = min(width, dp[k][j])
max_area = max(max_area, width * (i-k+1))

fisier_iesire.write(str(max_area))

if __name__ == '__main__':
fisier_intrare = open("hambarin.txt", "r") # declararea fisierelor
fisier_iesire = open("hambarout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
dim_n, dim_m = map(int, fisier_intrare.readline().split())
lista_pomi = [list(map(int, fisier_intrare.readline().split())) for _ in range(dim_m)]

validare(dim_n, dim_m, lista_pomi) # apelul functiei de validare
arie_maxima(dim_n, lista_pomi) # apelul functiei de rezolvare

except ValueError:
fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

1972 - Hambar - Revision history