AjM: Pagină nouă: == Enunt == Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător. Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, iden...

2024-06-03T17:35:50Z

Pagină nouă: == Enunt == Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător. Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, iden...

New page

== Enunt ==
Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.
== Cerinţa ==
Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din șirul ordonat al sumelor tuturor subtablourilor matricei A.
== Date de intrare ==
Fișierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spațiu, având semnificația din enunț. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.
== Date de ieșire ==
Fişierul de ieşire ssk.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 150
* 1 ≤ M ≤ 150
* 1 ≤ K ≤ numărul de termeni din şirul ordonat
* 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N și 1 ≤ j ≤ M
Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1.
== Exemplu ==
; ssk.in
2 3 14
3 2 7
4 1 0
; ssk.out
9
<br>

== Explicație ==
Șirul ordonat al tuturor sumelor subtablourilor matricei este

0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17

A patrusprezecea sumă este 9.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_subtable_sums(matrix):
n = len(matrix)
m = len(matrix[0])

# Initialize the cumulative sum matrix
cumulative_sum = [[0] * (m + 1) for _ in range(n + 1)]

# Calculate cumulative sum matrix
for i in range(1, n + 1):
for j in range(1, m + 1):
cumulative_sum[i][j] = matrix[i - 1][j - 1] + cumulative_sum[i - 1][j] + cumulative_sum[i][j - 1] - cumulative_sum[i - 1][j - 1]

# Calculate the sum of each subtable and store it in a list
subtable_sums = []
for i1 in range(1, n + 1):
for j1 in range(1, m + 1):
for i2 in range(i1, n + 1):
for j2 in range(j1, m + 1):
subtable_sum = cumulative_sum[i2][j2] - cumulative_sum[i2][j1 - 1] - cumulative_sum[i1 - 1][j2] + cumulative_sum[i1 - 1][j1 - 1]
subtable_sums.append(subtable_sum)

# Sort the list of subtable sums
subtable_sums.sort()

return subtable_sums

def main():
with open("ssk.in", "r") as fin:
N, M, K = map(int, fin.readline().split())
matrix = [list(map(int, fin.readline().split())) for _ in range(N)]

# Calculate subtable sums
subtable_sums = calculate_subtable_sums(matrix)

# Retrieve the K-th term
kth_term = subtable_sums[K - 1]

# Write the result to the output file
with open("ssk.out", "w") as fout:
fout.write(str(kth_term) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1228 - SSK - Revision history