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
1 2 0 1
sunt șase submatrice omogene, acestea fiind:

0 1 2
1 2 0

1 2 0
2 0 1

0 1 2

1 2 0

1 2 0

2 0 1

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 ⩽ l ⩽ c ⩽ 500
• 4 ⩽ l*c ⩽ 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>

1. 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>