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 ⩽ N, M ⩽ 30.000
• 1 ⩽ A ⩽ 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:

1 0 0 1
0 1 1 0

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:

(1,1) (1,4)
(2,1) (2,4)
(1,1) (2,2)
(1,2) (2,3)
(1,3) (2,4)

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>

1. 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>