Editing 3788 - Matricea

== Enunț ==
Se consideră o matrice binară B (cu valori 0 sau 1) cu N linii şi M coloane, liniile şi coloanele fiind numerotate de la 1 la N, respectiv de la 1 la M. Matricea B este generată după regula B[i][j] = R[i] xor C[j], unde R şi C sunt vectori binari de lungime N, respectiv M. Numim dreptunghi de colţuri (x1,y1) (x2,y2) cu x1 ≤ x2 şi y1 ≤ y2, mulţimea elementelor B[i][j] cu x1 ≤ i ≤ x2 și y1 ≤ j ≤ y2. Aria unui astfel de dreptunghi este (x2 - x1 + 1) * (y2 - y1 + 1).

== Cerința ==
Determinaţi numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

== Date de intrare ==
Fișierul de intrare matricein.txt conține pe prima linie pe prima linie numerele naturale N, M, A separate prin câte un spaţiu. A doua linie va conţine N valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului R, iar a treia linie va conţine M valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele vectorului C.

== Date de ieșire ==
Fișierul de ieșire matriceout.txt va conține o singură linie pe care vor fi scrise două numere naturale separate printr-un singur spaţiu Zmax Nsol, reprezentând în ordine numărul maxim de elemente egale cu 0 într-un dreptunghi a cărui arie este exact A, precum şi numărul de dreptunghiuri pentru care se obţine acest număr maxim.

== Restricții și precizări ==
* 1 &les; '''N, M''' &les; 30.000
* 1 &les; '''A''' &les; 5.000.000
* Prin xor se înţelege operatorul sau exclusiv (^ în C++). Mai exact: x ^ y = 1 dacă și numai dacă un operand este 0, iar celălalt 1, deci 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1.

== Exemplul 1 ==
; Intrare
; matricein.txt
: 2 4 4
: 0 1
: 1 0 0 1
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; matriceout.txt
: 2 5

=== Explicație ===
Matricea B este: <br>

1 0 0 1 <br>
0 1 1 0 <br>

Numărul maxim de valori 0 dintr-un dreptunghi de arie 4 este 2. Cele 5 dreptunghiuri de arie 4 cu număr maxim de 0 sunt:<br>

(1,1) (1,4)<br>
(2,1) (2,4)<br>
(1,1) (2,2)<br>
(1,2) (2,3)<br>
(1,3) (2,4)<br>

== Exemplul 2 ==
; Intrare
; matricein.txt
: 30001 4 4
: 0 1
: 1 0 0 1
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#3788 - Matricea

def validare_date(n, m, a, r, c):
    if not (1 <= n <= 30000) or not (1 <= m <= 30000) or not (1 <= a <= 5000000):
        return False
    if len(r) != n or len(c) != m:
        return False
    if not all(bit in {0, 1} for bit in r) or not all(bit in {0, 1} for bit in c):
        return False
    return True


def rezolva_problema(n, m, a, r, c):
    if validare_date(n, m, a, r, c):
        print("Datele de intrare corespund restricțiilor impuse")
        matrice = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                matrice[i][j] = r[i] ^ c[j]

        max_zeros = 0
        numar_dreptunghiuri = 0

        for x1 in range(n):
            for y1 in range(m):
                for x2 in range(x1, n):
                    for y2 in range(y1, m):
                        arie = (x2 - x1 + 1) * (y2 - y1 + 1)
                        if arie == a:
                            num_zeros = sum(matrice[i][j] == 0 for i in range(x1, x2 + 1) for j in range(y1, y2 + 1))
                            if num_zeros > max_zeros:
                                max_zeros = num_zeros
                                numar_dreptunghiuri = 1
                            elif num_zeros == max_zeros:
                                numar_dreptunghiuri += 1

        with open("matriceout.txt", "w") as f_out:
            f_out.write(f"{max_zeros} {numar_dreptunghiuri}\n")
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


with open("matricein.txt", "r") as f:
    n, m, a = map(int, f.readline().split())
    r = list(map(int, f.readline().split()))
    c = list(map(int, f.readline().split()))

rezolva_problema(n, m, a, r, c)

</syntaxhighlight>