Editing 2412 - Sub Mat 1

Se consideră o matrice <code>A</code> cu următoarele proprietăţi:

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

Definim o submatrice determinată de perechea de linii <code>L1</code> şi <code>L2</code> (<code>L1 ≤ L2</code>) şi de perechea de coloane <code>C1</code> şi <code>C2</code> (<code>C1 ≤ C2</code>) ca fiind totalitatea elementelor matricei <code>A[i,j]</code> pentru care <code>L1 ≤ i ≤ L2</code> şi <code>C1 ≤ j ≤ C2</code>.

Dacă toate elementele unei submatrice sunt egale cu <code>0</code>, atunci submatricea se numeşte nulă.

Asupra matricei <code>A</code> 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 <code>A</code> 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 <code>submat1IN.txt</code> conţine pe prima linie două numere naturale <code>n m</code>, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei <code>A</code>. Pe următoarele <code>n</code> linii ale fişierului sunt descrise cele <code>n</code> linii ale matricei <code>A</code>; pe fiecare linie din cele <code>n</code> vor fi scrise câte <code>m</code> valori din mulţimea <code>{0, 1}</code>, separate prin spaţii, reprezentând în ordine elementele liniei respective.

= Date de ieșire =
Fișierul de ieșire <code>submat1OUT.txt</code> 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 <code>A</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ n, m ≤ 1000</code>
* Pentru <code>60%</code> din teste <code>n, m ≤ 100</code>.

= Exemplul 1: =
<code>submat1IN.txt</code>
 3 5
 0 0 0 1 1
 0 1 1 1 1
 0 0 0 0 1
<code>submat1OUT.txt</code>
 6

=== Explicație ===
Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:

<code>0 0 0 1 1</code>

<code>0 0 0 0 1</code>

<code>0 1 1 1 1</code>

atunci se observă că submatricea determinată de prima şi a doua linie şi de prima şi a treia coloană conţine <code>6</code> valori de <code>0</code> (<code>6</code> fiind numărul maxim posibil).

== Exemplul 2: ==
<code>submat1IN.txt</code>
 1 5
 0 0 0 1 1
 0 1 1 1 1
 0 0 0 0 1
<code>submat1OUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
def verifica_restricii(n, m):
    return 2 <= n <= 1000 and 2 <= m <= 1000

def main():
    with open('submat1IN.txt', 'r') as fin:
        n, m = map(int, fin.readline().split())

    if not verifica_restricii(n, m):
        with open('submat1OUT.txt', 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return  
    a = [0] * n
    with open('submat1IN.txt', 'r') as fin:
        next(fin)  
        for i in range(n):
            linie = list(map(int, fin.readline().split()))
            a[i] = linie.count(0)

    a.sort(reverse=True)
    aria = 0
    for i in range(n):
        if aria < (i + 1) * a[i]:
            aria = (i + 1) * a[i]

    with open('submat1OUT.txt', 'w') as fout:
        fout.write(str(aria) + '\n')

if __name__ == '__main__':
    main()

</syntaxhighlight>