1687 - Omogene - Revision history

Vasiliu Costel Andrei: Pagină nouă: == 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

2024-01-01T10:22:13Z

Pagină nouă: == 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><b...

New page
== 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; '''lc''' &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 210^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>