Vizualizare sursă pentru „1687 - Omogene”

== Enunț ==
Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2. De exemplu, în matricea

0 1 2 0<br>
1 2 0 1<br>
sunt șase submatrice omogene, acestea fiind:<br>

0 1 2<br>
1 2 0 <br><br>
1 2 0<br>
2 0 1<br><br>
0 1 2<br><br>
1 2 0<br><br>
1 2 0<br><br>
2 0 1<br><br>
Submatricele a treia și a patra sunt formate din prima linie a matricei inițială, iar submatricele a cincea și a șasea sunt formate din a doua linie.

== Cerința ==
Să se determine câte submatrice nevide omogene există.

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

== Date de ieșire ==
Fișierul de ieșire omogeneout.txt va conține pe prima linie un singur număr natural reprezentând numărul submatricelor nevide omogene.

== Restricții și precizări ==
* 2 &les; '''l''' &les; '''c''' &les; 500
* 4 &les; '''l*c''' &les; 65536
* Atenție, o submatrice este formată dintr-o secvență continuă de linii și coloane, deci, de exemplu, dacă se aleg dintr-o matrice liniile 1, 2 și 5, atunci acestea nu formează o submatrice.
* Numărul submatricelor omogene va fi mai mic decât 2*10^9
* Întreaga matrice poate fi submatrice omogenă

== Exemplul 1 ==
; Intrare
; omogenein.txt
: 2 4
: 0 1 2 0
: 1 2 0 1
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; omogeneout.txt
: 6

=== Explicație ===
Cele șase submatrice au fost menționate în enunț.

== Exemplul 2 ==
; Intrare
; omogenein.txt
: 3 3
: 0 1 2
: 0 2 2
: 0 1 1
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; omogeneout.txt
: 3

== Exemplul 3 ==
; Intrare
; omogenein.txt
: 1 3
: 0 1 2
: 0 2 2
: 0 1 1
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#1687 - Omogene

def validare_date(l, c, matrice):
    if not (2 <= l <= c <= 5000):
        return False
    if not (4 <= l * c <= 65536):
        return False
    if len(matrice) != l or any(len(row) != c for row in matrice):
        return False
    return True


def numar_submatrici_omogene(l, c, matrice):
    if not validare_date(l, c, matrice):
        return 0

    numar_submatrici = 0

    for i in range(l):
        for j in range(c):
            for x in range(i, l):
                for y in range(j, c):
                    submatrice = [matrice[k][j:y + 1] for k in range(i, x + 1)]
                    numar_0 = sum(row.count(0) for row in submatrice)
                    numar_1 = sum(row.count(1) for row in submatrice)
                    numar_2 = sum(row.count(2) for row in submatrice)

                    if numar_0 == numar_1 == numar_2:
                        numar_submatrici += 1

    return numar_submatrici


with open("omogenein.txt", "r") as f:
    l, c = map(int, f.readline().split())
    matrice = [list(map(int, f.readline().split())) for _ in range(l)]

    if validare_date(l, c, matrice):
        print("Datele de intrare corespund restricțiilor impuse")

        rezultat = numar_submatrici_omogene(l, c, matrice)

        with open("omogeneout.txt", "w") as f:
            f.write(str(rezultat))

    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)

</syntaxhighlight>