Editing 2432 - Cruce

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>