2412 - Sub Mat 1

Se consideră o matrice A cu următoarele proprietăţi:

• conţine n linii şi m coloane;
• conţine doar valorile 0 şi 1;
• pe fiecare linie valorile sunt plasate în ordine crescătoare.

Definim o submatrice determinată de perechea de linii L1 şi L2 (L1 ≤ L2) şi de perechea de coloane C1 şi C2 (C1 ≤ C2) ca fiind totalitatea elementelor matricei A[i,j] pentru care L1 ≤ i ≤ L2 şi C1 ≤ j ≤ C2. Dacă toate elementele unei submatrice sunt egale cu 0, atunci submatricea se numeşte nulă. Asupra matricei A putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea A să conţină cel puţin o submatrice nulă cu număr maxim de elemente.

Cerința

Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.

Date de intrare

Fișierul de intrare submat1.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei A; pe fiecare linie din cele n vor fi scrise câte m valori din mulţimea {0, 1}, separate prin spaţii, reprezentând în ordine elementele liniei respective.

Date de ieșire

Fișierul de ieșire submat1.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.

Restricții și precizări

• 2 ≤ n, m ≤ 1000

• Pentru 60% din teste n, m ≤ 100.

Exemplul 1

submat1in.txt

3 5

0 0 0 1 1

0 1 1 1 1

0 0 0 0 1

submat1out.txt

6

Exemplul 2

submat1in.txt

4 2

0 0

1 1

0 1

0 0

submat1out.txt

5

Rezolvare

<syntaxhighlight lang="python" line>

1. 2412 - Sub Mat 1

def numar_maxim_zerouri(matrice):

   numar_linii = len(matrice)
   numar_coloane = len(matrice[0])

   matrice.sort(key=lambda linie: linie.count(0), reverse=True)

   prefixe = [linie.copy() for linie in matrice]
   for i in range(numar_linii):
       for j in range(1, numar_coloane):
           prefixe[i][j] += prefixe[i][j - 1]

   rezultat = 0

   for i in range(numar_linii):
       for j in range(i, numar_linii):
           numar_zerouri = prefixe[j][-1] if i == 0 else prefixe[j][-1] - prefixe[i - 1][-1]
           rezultat = max(rezultat, numar_zerouri * (j - i + 1))

   return rezultat

def verificare_restrictii(numar): # funcția de verificare a datelor de intrare

   if 2 <= n                    # adăugăm restricția pentru n
      m <= 1000
       return True
   else:
       return False

def main():

   with open("submat1in.txt", "r") as file_in:
       n, m = map(int, file_in.readline().split())
       matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]

   rezultat = numar_maxim_zerouri(matrice)

   with open("submat1out.txt", "w") as file_out:
       file_out.write(str(rezultat))

if __name__ == "__main__":

   main()

</syntaxhighlight>