2194 - identice3

Enunt

Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulțimea {0,1}. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 și invers. El vrea să aplice operația ZET inițial pentru matricea A, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat R, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.

Cerinta

Mihai vă roagă să calculați valorile K și R. Pentru a preciza tipul cerinței, Mihai folosește un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.

Date de intrare

Fișierul de intrare identice3.in se vor afla numerele naturale T, N și D, cu semnificația de mai sus, separate prin câte un spațiu. Pe următoarele N linii se vor afla câte N valori de 0 și 1, elementele liniilor matricei A, fără spații între ele.

Date de ieșire

Fișierul de ieșire identice3.out se va afla un număr natural, respectiv valoarea K pentru T = 1 sau valoarea R pentru T = 2.

Restrictii si precizari

1 < D < N ≤ 1000
Pentru calcularea valorii K, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv 1), cu elementele identice.

Exemplul 1

intrare

1 4 2

0011

1100

iesire

Datele introduse corespund restrictiilor impuse.

36

Exemplul 2

intrare

10 9 5

1100

1010

0011

0101

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

2194 - identice3

def count_K(N):

   K = 0
   for D in range(1, N+1):
       K += (N - D + 1) ** 2
   return K

def apply_ZET(matrix, D):

   new_matrix = [row.copy() for row in matrix]
   for i in range(len(matrix) - D + 1):
       for j in range(len(matrix[0]) - D + 1):
           for x in range(D):
               for y in range(D):
                   new_matrix[i + x][j + y] = 1 - matrix[i + x][j + y]
   return new_matrix

def count_R(matrix):

   R = 0
   while len(set(matrix[0])) > 1 or any(matrix[i] != matrix[0] for i in range(1, len(matrix))):
       matrix = apply_ZET(matrix, R + 1)
       R += 1
       if R > min(len(matrix), len(matrix[0])):
           return -1
   return R

if T == 1:

   K = count_K(N)
   print(f"Valoarea lui K este: {K}")

elif T == 2:

   R = count_R(matrix_A)
   print(f"Valoarea lui R este: {R}")

else:

   print("Valoarea T trebuie să fie 1 sau 2.")

</syntaxhighlight>