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