2665 - Dreptunghi1: Difference between revisions

Latest revision as of 11:57, 29 December 2023

Cerinta[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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

Restrictii si precizari[edit | edit source]

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

Punctaje partiale[edit | edit source]

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

Exemplul 1[edit | edit source]

dreptunghi1in.txt: 6 6 3; 4 1; 4 5; 3 3
dreptunghi1out.txt: Datele introduse corespund restrictiilor impuse; 12

Exemplul 2[edit | edit source]

dreptunghi1in.txt: 1 2; 0 0; -1 -2 -3

Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):

   if not (1 <= m <= 10000 and 1 <= n <= 10000 and 1 <= z <= 10000):
       return False

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

   if not (0 <= aria_maxima <= m * n):
       return False

   return True

Citire date de intrare

with open("dreptunghi1in.txt", "r") as f:

   m, n, z = map(int, f.readline().split())
   pozitii_0 = [tuple(map(int, f.readline().split())) for _ in range(z)]

Calculare aria maxima

aria_maxima = calculeaza_aria_maxima(m, n, z, pozitii_0)

Scriere rezultat în fișier de ieșire

with open("dreptunghi1out.txt", "w") as f_out:

   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>

Explicatie[edit | edit source]

Matricea este:

111111
111111: 110111; 011101; 111111; 111111

Cel mai mare dreptunghi are arie 12.

@@ Line 1: / Line 1: @@
 == 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 ==
-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 ==
-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 ==
-*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.
@@ Line 22: / Line 22: @@
 == Exemplul 1 ==
-;Intrare
+;dreptunghi1in.txt
 :6 6 3
 :4 1
 :4 5
 :3 3
-;Iesire
+;dreptunghi1out.txt
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :12
 == Exemplul 2 ==
-;Intrare
+;dreptunghi1in.txt
 :1 2
 :0 0
 :-1 -2 -3
-;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def arie_maxima_dreptunghi(matrix):
+def verificare_rezultat_corect(m, n, z, pozitii_0, aria_maxima):
-     def arie_histograma_maxima(inaltimi):
+     if not (1 <= m <= 10000 and 1 <= n <= 10000 and 1 <= z <= 10000):
-        stack = []
+         return False
-        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
+     for lin, col in pozitii_0:
+        if not (0 <= lin < m and 0 <= col < n):
+            return False
-def main():
+     if not (0 <= aria_maxima <= m * n):
-     with open("dreptunghi1.txt", "r") as fisier:
+         return False
-        m, n, z = map(int, fisier.readline().split())
-         matrice = [[1] * n for _ in range(m)]
-        for _ in range(z):
+    return True
-            linie, coloana = map(int, fisier.readline().split())
-            matrice[linie - 1][coloana - 1] = 0
-     rezultat = arie_maxima_dreptunghi(matrice)
+# Citire date de intrare
+with open("dreptunghi1in.txt", "r") as f:
+    m, n, z = map(int, f.readline().split())
+     pozitii_0 = [tuple(map(int, f.readline().split())) for _ in range(z)]
-    with open("dreptunghi1.txt", "w") as fisier_out:
+# Calculare aria maxima
-        fisier_out.write(str(rezultat))
+aria_maxima = calculeaza_aria_maxima(m, n, z, pozitii_0)
-if __name__ == "__main__":
+# Scriere rezultat în fișier de ieșire
-    main()
+with open("dreptunghi1out.txt", "w") as f_out:
+    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>