2665 - Dreptunghi1

From Bitnami MediaWiki
Revision as of 10:21, 27 December 2023 by Mesarosdenisa (talk | contribs)

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 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 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;
  • 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

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

Exemplul 2

dreptunghi1in.txt
1 2
0 0
-1 -2 -3
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.