2429 - matrice9: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Cerinta == Se cere să se găsească o submatrice validă a lui A de arie maximă. == Date de intrare == Fișierul de intrare matrice9.in conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A. == Date de iesire == Fișierul de ieșire matrice9.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l...
 
No edit summary
Line 48: Line 48:
== Rezolvare ==
== Rezolvare ==


<syntaxhighlightlang="python3"line="1">
<syntaxhighlight lang="python"line=">


#2429 - matrice9
def este_sir_valid(sir):
def este_sir_valid(sir):
     n = len(sir)
     n = len(sir)
Line 75: Line 76:


     return max_aria
     return max_aria
# Exemplu de folosire
matrice_A = [
    [1, 2, 3, 7],
    [8, 5, 2, 1],
    [3, 5, 6, 2],
    [4, 1, 5, 6]
]
rezultat = aria_maxima_submatrice_valida(matrice_A)
print("Aria maxima a unei submatrici valide este:", rezultat)


<syntaxhighlight>
<syntaxhighlight>

Revision as of 10:48, 14 December 2023

Cerinta

Se cere să se găsească o submatrice validă a lui A de arie maximă.

Date de intrare

Fișierul de intrare matrice9.in conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

Date de iesire

Fișierul de ieșire matrice9.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

Restrictii si precizari

  • 1 ≤ N, M ≤ 1000
  • 70% din teste vor avea N, M ≤ 600
  • Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

Exemplul 1

intrare
2 6
1 2 5 7 9 10
3 4 3 5 1 10
iesire
Datele introduse corespund restrictiilor impuse.
1 1 2 3

Exemplul 2

intrare
3 7
2 3 6 8 10 11
4 5 4 6 2 11
iesire
Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python"line=">

  1. 2429 - matrice9

def este_sir_valid(sir):

   n = len(sir)
   crescator = all(sir[i] < sir[i + 1] for i in range(n - 1))
   descrescator = all(sir[i] > sir[i + 1] for i in range(n - 1))
   return crescator or descrescator

def aria_maxima_submatrice_valida(matrice):

   n = len(matrice)
   m = len(matrice[0])
   max_aria = 0
   for i in range(n):
       for j in range(m):
           sir_linie = [matrice[i][k] for k in range(j, m)]
           submatrice_aria = 0
           for h in range(i, n):
               sir_linie = [matrice[h][k] for k in range(j, m)]
               if este_sir_valid(sir_linie):
                   submatrice_aria += len(sir_linie)
                   max_aria = max(max_aria, submatrice_aria)
               else:
                   break
   return max_aria

<syntaxhighlight>