2425 - Peri: Diferență între versiuni
(Pagină nouă: Se consideră o matrice dreptunghiulară <code>A</code> cu <code>m</code> linii şi <code>n</code> coloane cu valori <code>0</code> sau <code>1</code>, liniile şi coloanele fiind numerotate de la <code>1</code> la <code>m</code>, respectiv de la <code>1</code> la <code>n</code>. Numim dreptunghi de colţuri <code>(x1, y1) (x2,y2)</code> cu <code>x1 < x2</code> şi <code>y1 < y2</code> mulţimea elementelor <code>A[i][j]</code> cu <code>x1 ≤ i ≤ x2</code> si <code>y1 ≤...) |
Fără descriere a modificării |
||
Linia 5: | Linia 5: | ||
= Date de intrare = | = Date de intrare = | ||
Fișierul de intrare <code>peri.in</code> conține pe prima linie numerele <code>m</code> şi <code>n</code>, separate printr-un singur spaţiu. Pe următoarele <code>m</code> linii este dată matricea <code>A</code>, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.<syntaxhighlight lang="python" line="1"> | Fișierul de intrare <code>peri.in</code> conține pe prima linie numerele <code>m</code> şi <code>n</code>, separate printr-un singur spaţiu. Pe următoarele <code>m</code> linii este dată matricea <code>A</code>, numerele de pe aceeaşi linie fiind separate de câte un spaţiu. | ||
= Date de ieșire = | |||
Fișierul de ieșire <code>peri.out</code> va conţine o singură linie pe care se află două numere întregi separate printr-un spaţiu. Primul număr este diferenţa maximă dintre numărul de elemente <code>1</code> şi numărul de elemente <code>0</code> de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente <code>1</code> şi numărul de elemente <code>0</code> de pe perimetru este maximă. | |||
= Restricții și precizări = | |||
* <code>1 ≤ m, n ≤ 250</code> | |||
* Prin diferenţă nu se înţelege diferenţă în valoare absolută! | |||
= Exemplu: = | |||
<code>peri.in</code> | |||
4 5 | |||
1 0 0 1 0 | |||
0 1 1 0 0 | |||
0 1 0 1 0 | |||
1 1 1 0 1 | |||
<code>peri.out</code> | |||
4 2 | |||
<syntaxhighlight lang="python" line="1"> | |||
def max_perimeter_diff(matrix): | def max_perimeter_diff(matrix): | ||
m = len(matrix) | m = len(matrix) | ||
Linia 64: | Linia 82: | ||
print(f"Numărul de dreptunghiuri: {count_max_diff_rects}") | print(f"Numărul de dreptunghiuri: {count_max_diff_rects}") | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Versiunea curentă din 31 iulie 2024 12:56
Se consideră o matrice dreptunghiulară A
cu m
linii şi n
coloane cu valori 0
sau 1
, liniile şi coloanele fiind numerotate de la 1
la m
, respectiv de la 1
la n
. Numim dreptunghi de colţuri (x1, y1) (x2,y2)
cu x1 < x2
şi y1 < y2
mulţimea elementelor A[i][j]
cu x1 ≤ i ≤ x2
si y1 ≤ j ≤ y2
. Numim perimetru al dreptunghiului de colţuri (x1, y1) (x2, y2)
mulţimea elementelor A[i][j]
pentru care (i = x1
şi y1 ≤ j ≤ y2
) sau (i = x2
şi y1 ≤ j ≤ y2
) sau (j = y1
şi x1 ≤ i ≤ x2
) sau (j = y2
şi x1 ≤ i ≤ x2
).
Cerința
Determinaţi diferenţa maximă dintre numărul de elemente egale cu 1
şi numărul de elemente egale cu 0
aflate pe perimetrul aceluiaşi dreptunghi, precum şi numărul de dreptunghiuri pentru care se obţine această diferenţă.
Date de intrare
Fișierul de intrare peri.in
conține pe prima linie numerele m
şi n
, separate printr-un singur spaţiu. Pe următoarele m
linii este dată matricea A
, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.
Date de ieșire
Fișierul de ieșire peri.out
va conţine o singură linie pe care se află două numere întregi separate printr-un spaţiu. Primul număr este diferenţa maximă dintre numărul de elemente 1
şi numărul de elemente 0
de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente 1
şi numărul de elemente 0
de pe perimetru este maximă.
Restricții și precizări
1 ≤ m, n ≤ 250
- Prin diferenţă nu se înţelege diferenţă în valoare absolută!
Exemplu:
peri.in
4 5 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1
peri.out
4 2
def max_perimeter_diff(matrix):
m = len(matrix)
n = len(matrix[0])
max_diff = float('-inf')
count_max_diff_rects = 0
# Helper function to count 1's and 0's on the perimeter
def count_perimeter(x1, y1, x2, y2):
ones = 0
zeros = 0
for j in range(y1, y2 + 1):
if matrix[x1][j] == 1:
ones += 1
else:
zeros += 1
if matrix[x2][j] == 1:
ones += 1
else:
zeros += 1
for i in range(x1 + 1, x2):
if matrix[i][y1] == 1:
ones += 1
else:
zeros += 1
if matrix[i][y2] == 1:
ones += 1
else:
zeros += 1
return ones, zeros
# Iterate over all possible top-left corners (x1, y1)
for x1 in range(m - 1):
for y1 in range(n - 1):
# Iterate over all possible bottom-right corners (x2, y2)
for x2 in range(x1 + 1, m):
for y2 in range(y1 + 1, n):
ones, zeros = count_perimeter(x1, y1, x2, y2)
diff = ones - zeros
if diff > max_diff:
max_diff = diff
count_max_diff_rects = 1
elif diff == max_diff:
count_max_diff_rects += 1
return max_diff, count_max_diff_rects
# Exemplu de utilizare
matrix = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
max_diff, count_max_diff_rects = max_perimeter_diff(matrix)
print(f"Diferența maximă: {max_diff}")
print(f"Numărul de dreptunghiuri: {count_max_diff_rects}")