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
.
Cerința
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 identice3IN.txt
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 identice3OUT.txt
se va afla un număr natural, respectiv valoarea K
pentru T = 1
sau valoarea R
pentru T = 2
.
Restricții și precizări
1 < D < N ≤ 1000
- Pentru calcularea valorii
K
, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv1
), cu elementele identice.
Exemplul 1:
identice3IN.txt
1 4 2 0011 0011 1100 1100
identice3OUT.txt
36
Explicație
T = 1
, deci se calculează K = 36
. Sunt 18
submatrice cu toate elementele 0
și 18
cu toate elementele 1
.
Exemplul 2:
identice3IN.txt
2 4 2 0011 0011 1100 1100
identice3OUT.txt
2
Explicație
T = 2
, deci se calculează R = 2
, deoarece sunt necesare 2
aplicări ale operației ZET.
Exemplul 3:
identice3IN.txt
1 1001 2 0011 0011 1100 1100
identice3OUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
Nmax = 1005
opus = {'0': '1', '1': '0'}
t0 = [[0] * Nmax for _ in range(Nmax)]
st0 = [0] * Nmax
val0 = [0] * Nmax
t1 = [[0] * Nmax for _ in range(Nmax)]
st1 = [0] * Nmax
val1 = [0] * Nmax
M0 = [[0] * Nmax for _ in range(Nmax)]
M1 = [[0] * Nmax for _ in range(Nmax)]
p0 = [0] * Nmax
p1 = [0] * Nmax
def check_restrictions():
return 1 < d < n <= 1000
def read():
global test, n, d, a, a1
with open("identice3IN.txt", 'r') as in_file:
test, n, d = map(int, in_file.readline().split())
if not check_restrictions():
return False
a = [[''] * (n + 2) for _ in range(n + 2)] # Adjusted size
a1 = [[''] * (n + 1) for _ in range(n + 1)] # Adjusted size
for i in range(1, n + 1):
a[i][1:n + 1] = in_file.readline().strip()
for j in range(1, n + 1):
a1[i][j] = opus[a[i][j]]
return True
def solve0():
global sum0, a
sum0 = 0
for j in range(1, n + 1):
vf0 = 0
for i in range(1, n + 1):
if a[i][j] == '0':
t0[i][j + 1] = 1 + t0[i][j]
m = 1
while vf0 > 0 and st0[vf0] >= t0[i][j + 1]:
m += val0[vf0]
vf0 -= 1
vf0 += 1
st0[vf0] = t0[i][j + 1]
val0[vf0] = m
sum0 += val0[vf0] * st0[vf0]
def solve1():
global sum1, a
sum1 = 0
for j in range(1, n + 1):
vf1 = 0
for i in range(1, n + 1):
if a[i][j] == '1':
t1[i][j + 1] = 1 + t1[i][j]
m = 1
while vf1 > 0 and st1[vf1] >= t1[i][j + 1]:
m += val1[vf1]
vf1 -= 1
vf1 += 1
st1[vf1] = t1[i][j + 1]
val1[vf1] = m
sum1 += val1[vf1] * st1[vf1]
def R0():
global sol0, a
sol0 = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
M0[i][j] += M0[i - 1][j]
p0[j] = p0[j - 1] + M0[i][j]
t = p0[j] & 1
if i > n - d + 1 or j > n - d + 1:
if t != int(a[i][j]):
return -1
elif t != int(a[i][j]):
sol0 += 1
M0[i][j] += 1
M0[i + d][j] -= 1
M0[i][j + d] -= 1
M0[i + d][j + d] += 1
p0[j] += 1
return sol0
def R1():
global sol1, a
sol1 = 0
for i in range(1, n + 1):
for j in range(1, n + 1):
M1[i][j] += M1[i - 1][j]
p1[j] = p1[j - 1] + M1[i][j]
t = p1[j] & 1
if i > n - d + 1 or j > n - d + 1:
if t != int(a1[i][j]):
return -1
elif t != int(a1[i][j]):
sol1 += 1
M1[i][j] += 1
M1[i + d][j] -= 1
M1[i][j + d] -= 1
M1[i + d][j + d] += 1
p1[j] += 1
return sol1
def main():
if not read():
with open("identice3OUT.txt", 'w') as out_file:
out_file.write("Datele nu corespund restrictiilor impuse\n")
return
if test == 1:
solve0()
solve1()
with open("identice3OUT.txt", 'w') as out_file:
out_file.write(str(sum0 + sum1) + '\n')
else:
R0_result = R0()
R1_result = R1()
rx = min(R0_result, R1_result)
ry = max(R0_result, R1_result)
if rx == -1:
rx = ry
with open("identice3OUT.txt", 'w') as out_file:
out_file.write(str(rx) + '\n')
if __name__ == "__main__":
main()