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 (inclusiv 1), 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()