Editing 2194 - identice3 (section)

= Exemplul 2: =
<code>identice3IN.txt</code>
 2 4 2
 0011
 0011
 1100
 1100
<code>identice3OUT.txt</code>
 2

=== Explicație ===
<code>T = 2</code>, deci se calculează <code>R = 2</code>, deoarece sunt necesare <code>2</code> aplicări ale operației ZET.

== Exemplul 3: ==
<code>identice3IN.txt</code>
 1 1001 2
 0011
 0011
 1100
 1100
<code>identice3OUT.txt</code>
 Datele nu corespund restrictiilor impuse

=== Rezolvare ===
<syntaxhighlight lang="python3" line="1">
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()

</syntaxhighlight>