3290 - Mat D3

Enunț

Fie o matrice cu L linii și C coloane care memorează numere naturale. O submatrice a sa având colțul stânga-sus (xs, ys) și colțul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] și indicele coloanei în intervalul [ys, yd]. O submatrice poate fi formată dintr-un singur element.

Cerința

Scrieți un program care determină numărul submatricelor care au suma elementelor divizibilă cu 3.

Date de intrare

Fișierul de intrare matd3in.txt conține pe prima linie numerele naturale L și C separate prin spațiu. Pe următoarele L linii se află câte C numere naturale separate prin câte un spațiu reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire matd3out.txt va conține pe prima linie un singur număr natural K, reprezentând numărul submatricelor care au suma divizibilă cu 3.

Restricții și precizări

• 2 ⩽ L, C ⩽ 300
• elementele matricei sunt numere naturale cuprinse între 0 și 10.000
• numărul 0 este divizibil cu 3

Exemplul 1

Intrare

matd3in.txt

2 3

1 2 2

2 1 3

Ieșire

Datele de intrare corespund restricțiilor impuse

matd3out.txt

7

Explicație

Cele șapte submatrice sunt:

(1 2)
(2 1)
(2 1 3)
(3)
(1
2)
(2
1)
(1 2
2 1)

Exemplul 2

Intrare

matd3in.txt

1 3

1 2 2

2 1 3

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#3290 - Matd3

def validare_date(linii, coloane, matrice):
    if not (2 <= linii <= 300 and 2 <= coloane <= 300):
        return False
    for randuri in matrice:
        if len(randuri) != coloane or any(not (0 <= numere <= 10000) for numere in randuri):
            return False
    return True


def numarare_submatrici(linii, coloane, matrice):
    count = 0
    for xs in range(linii):
        for ys in range(coloane):
            for xd in range(xs, linii):
                for yd in range(ys, coloane):
                    submatrice_sum = sum(matrice[i][j] for i in range(xs, xd + 1) for j in range(ys, yd + 1))
                    if submatrice_sum % 3 == 0:
                        count += 1
    return count


def main():
    with open("matd3in.txt", "r") as file:
        linii, coloane = map(int, file.readline().split())
        matrice = [list(map(int, line.split())) for line in file]

    if validare_date(linii, coloane, matrice):
        print("Datele de intrare corespund restricțiilor impuse")
        result = numarare_submatrici(linii, coloane, matrice)
        with open("matd3out.txt", "w") as file_out:
            file_out.write(str(result))
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


if __name__ == "__main__":
    main()