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 ⩽ n, A, B, C, D ⩽ 400
• 1 ⩽ T ⩽ 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ă.
  

Exemplu 2

Intrare

0 0 0 0 0 0

Ieșire

Nu au fost respectate cerintele impuse

Rezolvare

#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()