RaulOtet at 12:56, 31 July 2024

2024-07-31T12:56:09Z

@@ Line 5: / Line 5: @@
 = 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.
 def max_perimeter_diff(matrix):
      m = len(matrix)
@@ Line 64: / Line 82: @@
 print(f"Numărul de dreptunghiuri: {count_max_diff_rects}")
 </syntaxhighlight>

RaulOtet: Pagină nouă: 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 ≤...`


2024-07-31T12:55:23Z
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 ≤...
New page
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 ≤ j ≤ y2</code>. Numim perimetru al dreptunghiului de colţuri <code>(x1, y1) (x2, y2)</code> mulţimea elementelor <code>A[i][j]</code> pentru care (<code>i = x1</code> şi <code>y1 ≤ j ≤ y2</code>) sau (<code>i = x2</code> şi <code>y1 ≤ j ≤ y2</code>) sau (<code>j = y1</code> şi <code>x1 ≤ i ≤ x2</code>) sau (<code>j = y2</code> şi <code>x1 ≤ i ≤ x2</code>).



= Cerința =

Determinaţi diferenţa maximă dintre numărul de elemente egale cu <code>1</code> şi numărul de elemente egale cu <code>0</code> 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 <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">

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}")

</syntaxhighlight>



= 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

2425 - Peri - Revision history

RaulOtet at 12:56, 31 July 2024