Editing 2943 - Maru

== Enunt ==
Se dă o matrice pătratică de n x n numere naturale și o valoare naturală T. Suma unei submatrice este suma elementelor submatricei.
== Cerința ==
Să se determine numărul submatricelor care au suma mai mică sau egală cu T.
== Date de intrare ==
Programul citește de la tastatură, în această ordine, numerele T n A B C D. Elementele matricei se vor genera după formula: a[i,j] = (A * i + B * j + C) % D.
== Date de ieșire ==
Programul va afișa pe ecran numărul S, reprezentând numărul submatricelor de sumă mai mică sau egală cu T.
== Restricții și precizări ==
*1 &les; n, A, B, C, D &les; 400
*1 &les; T &les; 30.000
*O submatrice poate fi formată dintr-un singur element (este o submatrice cu o linie și o coloană).
== Exemplu 1 ==
;Intrare
:10 2 1 1 1 43
;Ieșire
:9
;Explicație
*Matricea generată este:
:3 4
:4 5
*Singura submatrice care nu are suma mai mică sau egală cu T este doar matricea întreagă.<br>
== Exemplu 2 ==
; Intrare
: 0 0 0 0 0 0
; Ieșire
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2943 - Maru
def is_valid_input(n, T, A, B, C, D):
    if not (1 <= n <= 400 and 1 <= A <= 400 and 1 <= B <= 400 and 1 <= C <= 400 and 1 <= D <= 400):
        return False

    if not (1 <= T <= 30000):
        return False

    return True

def generate_matrix(n, A, B, C, D):
    matrix = [[(A * i + B * j + C) % D for j in range(n)] for i in range(n)]
    return matrix

def count_submatrices(matrix, T):
    n = len(matrix)
    count = 0

    for i in range(n):
        for j in range(n):
            for k in range(i, n):
                for l in range(j, n):
                    submatrix_sum = sum(matrix[x][y] for x in range(i, k + 1) for y in range(j, l + 1))
                    if submatrix_sum <= T:
                        count += 1

    return count

def main():
    try:
        T, n, A, B, C, D = map(int, input("Introduceti T n A B C D: ").split())
    except ValueError:
        print("Nu au fost respectate cerintele impuse.")
        return

    if not is_valid_input(n, T, A, B, C, D):
        print("Nu au fost respectate cerintele impuse.")
        return

    matrix = generate_matrix(n, A, B, C, D)
    result = count_submatrices(matrix, T)

    print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>