View source for 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 &les; '''L, C''' &les; 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) <br>
(2 1) <br>
(2 1 3)<br>
(3)<br>
(1<br>2) <br>
(2<br>1)<br>
(1 2<br>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 ==
<syntaxhighlight lang="python" line>
#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()

</syntaxhighlight>