Vasiliu Costel Andrei: Pagină nouă: == 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 - x...

2023-12-18T11:57:18Z

Pagină nouă: == 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 - x...

New page

== 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: 

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>
#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>

3788 - Matricea - Revision history