RaulOtet: Pagină nouă: Se consideră o matrice pătratică de dimensiune `N`, conţinând numere naturale. Numim '''cruce de lăţime''' `K` reuniunea mulțimii tuturor elementelor aflate pe `K` linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe `K` coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cr...

2024-07-26T08:17:41Z

Pagină nouă: Se consideră o matrice pătratică de dimensiune <code>N</code>, conţinând numere naturale. Numim '''cruce de lăţime''' <code>K</code> reuniunea mulțimii tuturor elementelor aflate pe <code>K</code> linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe <code>K</code> coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cr...

New page

Se consideră o matrice pătratică de dimensiune <code>N</code>, conţinând numere naturale. Numim '''cruce de lăţime''' <code>K</code> reuniunea mulțimii tuturor elementelor aflate pe <code>K</code> linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe <code>K</code> coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cruci, în formă de <code>T</code> sau <code>L</code>, când una dintre liniile sau coloanele care formează crucea sunt chiar la marginea matricei. Vom defini '''valoarea''' unei cruci ca fiind suma elementelor din care aceasta este formată.

= Cerința =
Scrieți un program care, pentru o valoare <code>K</code> dată, determină o cruce de lățime <code>K</code> a cărei valoare este maximă și poziția ei în matrice. Această poziție va fi exprimată prin perechea de indici reprezentând prima linie din cele <code>K</code> consecutive și prima coloană din cele <code>K</code> consecutive din care este formată crucea.

= Date de intrare =
Fişierul <code>cruce.in</code> conţine pe prima linie numerele <code>N</code> şi <code>K</code>, iar pe următoarele <code>N</code> linii câte <code>N</code> numere întregi reprezentând în ordine, pe linii, elementele matricei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

= Date de ieșire =
Fişierul <code>cruce.out</code> va conţine trei numere <code>Vmax L C</code>, separate prin câte un spaţiu, reprezentând valoarea maximă determinată pentru o cruce de lățime <code>K</code>, respectiv linia și coloana care exprimă poziția acesteia în matrice.

= Restricții și precizări =

* <code>1 ≤ N ≤ 500</code>
* <code>1 ≤ K < N</code>
* Numerele din matrice sunt din intervalul <code>[-5000, 5000]</code>
* Liniile şi coloanele se indexează începând cu <code>1</code>.
* Dacă există mai multe cruci de lățime <code>K</code> de valoare maximă, se va lua în considerare poziția cu indicele '''liniei''' mai mic, iar în caz de egalitate a liniilor poziția celei cu indicele '''coloanei''' mai mic.
* La olimpiadă s-au oferit 10 puncte din oficiu, aici vor fi date pe exemple.

= Exemplu: =
<code>cruce.in</code>
5 2
1 -2 3 -1 4
-3 2 2 -2 -1
1 2 3 4 5
1 0 -7 1 1
3 2 1 2 3
<code>cruce.out</code>
23 2 4

=== Explicație ===
Elementele ce formează crucea de valoare maxima sunt:

1 -2 3 <code>-1 4</code>

<code>-3 2 2 -2 -1</code>

<code>1 2 3 4 5</code>

1 0 -7 <code>1 1</code>

3 2 1 <code>2 3</code>

<syntaxhighlight lang="python" line="1">
def calculeaza_prefix_sum(matrice, N):
prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
for j in range(1, N + 1):
prefix_sum[i][j] = matrice[i - 1][j - 1] \
+ prefix_sum[i - 1][j] \
+ prefix_sum[i][j - 1] \
- prefix_sum[i - 1][j - 1]
return prefix_sum

def suma_submatrice(prefix_sum, x1, y1, x2, y2):
return (prefix_sum[x2][y2]
- prefix_sum[x1 - 1][y2]
- prefix_sum[x2][y1 - 1]
+ prefix_sum[x1 - 1][y1 - 1])

def cruce_maxima(matrice, N, K):
prefix_sum = calculeaza_prefix_sum(matrice, N)
max_valoare = -1
max_pos = (0, 0)

for i in range(1, N - K + 2):
for j in range(1, N - K + 2):
# Suma liniilor K consecutive
suma_linii = 0
for r in range(K):
suma_linii += suma_submatrice(prefix_sum, i + r, j, i + r, j + K - 1)

# Suma coloanelor K consecutive
suma_coloane = 0
for c in range(K):
suma_coloane += suma_submatrice(prefix_sum, i, j + c, i + K - 1, j + c)

# Calculul valorii crucii
suma_cruce = suma_linii + suma_coloane - suma_submatrice(prefix_sum, i, j, i + K - 1, j + K - 1)

if suma_cruce > max_valoare:
max_valoare = suma_cruce
max_pos = (i, j)

return max_valoare, max_pos

def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])
matrice = []

index = 2
for _ in range(N):
matrice.append([int(x) for x in data[index:index + N]])
index += N

max_valoare, max_pos = cruce_maxima(matrice, N, K)
print(max_valoare)
print(max_pos[0], max_pos[1])

if __name__ == "__main__":
main()
</syntaxhighlight>

2432 - Cruce - Revision history