Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03599 (python)

Fixed submission:
A, B, C, D, E, F = map(int, input().split())

d = 0
for i in range(31):
    if i * 100 * A > F:
        break
    for j in range(31):
        if i * 100 * A + j * 100 * B > F:
            break
        if i == 0 and j == 0:
            break
        for k in range(0, 1501, C):
            if k > i * A * E + j * B * E:
                break
            m = i * 100 * A + j * 100 * B + k
            if m > F:
                break
            l1 = F - m
            l2 = i * A * E + j * B * E - k
            l = min(l1, l2)
            l = int(l / D) * D
            d1 = 100 * (k + l) / (m + l)
            if d < d1:
                w = m + l
                s = k + l
                d = d1
if d == 0:
    if 100 * A <= F:
        print('{0} {1}'.format(100 * A, 0))
    else:
        print('{0} {1}'.format(100 * B, 0))
else:
    print('{0} {1}'.format(w, s))

Buggy submission (verdict: Runtime Error):
A, B, C, D, E, F = map(int, input().split())

d = 0
for i in range(31):
    if i * 100 * A > F:
        break
    for j in range(31):
        if i * 100 * A + j * 100 * B > F:
            break
        if i == 0 and j == 0:
            break
        for k in range(0, 1501, C):
            if k > i * A * E + j * B * E:
                break
            m = i * 100 * A + j * 100 * B + k
            if m > F:
                break
            l1 = F - m
            l2 = i * A * E + j * B * E - k
            l = min(l1, l2)
            l = int(l / D) * D
            d1 = 100 * (k + l) / (m + l)
            if d < d1:
                w = m + l
                s = k + l
                d = d1
print('{0} {1}'.format(w, s))
Problem p03611 (python)

Fixed submission:
import collections
N = int(input())
a = (list(map(int, input().split())))
for i in range(N):
    a.append(a[i] - 1)
    a.append(a[i] + 1)
c = collections.Counter(a)
print(c.most_common()[0][1])

Buggy submission (verdict: Runtime Error):
import sys
N = int(input())
a = sorted(list(map(int, input().split())))

X = 0
c = 1
i = 0
while True:
    if i == N - 1:
        X = max(X, c)
        break
    a_0 = a[i]
    a_1 = a[i] - 1
    a_2 = a[i] + 1
    while True:
        b_0 = a[i + 1]
        b_1 = a[i + 1] - 1
        b_2 = a[i + 1] + 1
        b = [b_0, b_1, b_2]
        if a_0 in b or a_1 in b or a_2 in b:
            c += 1
            i += 1
        else:
            X = max(X, c)
            c = 1
            i += 1
            break
print(X)
Problem p03638 (python)

Fixed submission:
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in range(N):
    D[i + 1] = A[i]
C = []
for k, v in D.items():
    [C.append(k) for _ in range(v)]
h = 0
while True:
    h += 1
    for i in range(W):
        print(C[i], end=' ')
    print('')
    [C.pop(0) for _ in range(W)]
    if h == H:
        break
    h += 1
    for i in reversed(range(W)):
        print(C[i], end=' ')
    print('')
    [C.pop(0) for _ in range(W)]
    if h == H:
        break

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in range(N):
    D[i + 1] = A[i]
C = ''
for k, v in D.items():
    C += v * str(k)
while True:
    c = C[:W]
    for i in range(W):
        print(c[i], end=' ')
    print('')
    if len(C) == W:
        break
    C = C[W:]
    c = C[:W]
    for i in range(W - 1, -1, -1):
        print(c[i], end=' ')
    print('')
    if len(C) == W:
        break
    C = C[W:]

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in range(N):
    D[i + 1] = A[i]
D = sorted(D.items(), key=lambda x: x[1], reverse=True)
C = ''
for d in D:
    C += d[1] * str(d[0])
while True:
    c = C[:W]
    for i in range(W):
        print(c[i], end=' ')
    print('')
    if len(C) == W:
        break
    C = C[W:]
    c = C[:W]
    for i in range(W - 1, -1, -1):
        print(c[i], end=' ')
    print('')
    if len(C) == W:
        break
    C = C[W:]
Problem p03680 (python)

Fixed submission:
import sys
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
b = [0] * N
i = 0
c = 1
while True:
    if b[i] == 1:
        print(-1)
        sys.exit()
    b[i] = 1
    i = a[i] - 1
    if i == 1:
        print(c)
        sys.exit()
    c += 1

Buggy submission (verdict: Runtime Error):
import sys
N = int(input())
a = [int(input()) for i in range(N)]
d = [0]
b = 0
c = 0
while True:
    if b == 1:a
        print(c)
        sys.exit()
    c += 1
    b = a[b] - 1
    if b in d:
        print('-1')
        sys.exit()
    d.append(b)
Problem p03944 (python)

Fixed submission:
W, H, N = map(int, input().split())
X = [list(map(int, input().split())) for i in range(N)]
M = [[0] * W for i in range(H)]
for x in X:
    if x[2] == 1:
        for i in range(0, x[0]):
            for j in range(H):
                M[j][i] = 1
    elif x[2] == 2:
        for i in range(x[0], W):
            for j in range(H):
                M[j][i] = 1
    elif x[2] == 3:
        for i in range(0, x[1]):
            for j in range(W):
                M[i][j] = 1
    elif x[2] == 4:
        for i in range(x[1], H):
            for j in range(W):
                M[i][j] = 1
c = 0
for i in range(W):
    for j in range(H):
        if M[j][i] == 0:
            c += 1
print(c)

Buggy submission (verdict: Runtime Error):
W, H, N = map(int, input().split())
xya = [list(map(int, input().split())) for _ in range(N)]

S = [[1] * W for _ in range(H)]
for x, y, a in xya:
    if a == 1:
        for i in range(H):
            for j in range(x):
                S[i][j] = 0
    elif a == 2:
        for i in range(x, W):
            for j in range(x, W)
                S[i][j] = 0
    elif a == 3:
        for i in range(y):
            for j in range(W):
                S[i][j] = 0
    else:
        for i in range(y, H):
            for j in range(W):
                S[i][j] = 0
print(sum(S))

Buggy submission (verdict: Runtime Error):
W, H, N = map(int, input().split())
xya = [list(map(int, input().split())) for _ in range(N)]

S = [[1] * W for _ in range(H)]
for x, y, a in xya:
    if a == 1:
        for i in range(H):
            for j in range(x):
                S[i][j] = 0
    elif a == 2:
        for i in range(x, W):
            for j in range(x, W)
                S[i][j] = 0
    elif a == 3:
        for i in range(y):
            for j in range(W):
                S[i][j] = 0
    else:
        for i in range(y, H):
            for j in range(W):
                S[i][j] = 0
print(sum(S))
Problem p02608 (python)

Fixed submission:
n = int(input())

ans = [0] * n
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a >= 1 and a <= n:
                ans[a - 1] += 1

for a in ans:
    print(a)

Buggy submission (verdict: Runtime Error):
from math import sqrt
from math import floor
n = int(input())

for i in range(n + 1):
    n2 = floor(sqrt(i))
    ans = 0
    for x in range(1, n2):
        for y in range(1, n2):
            if i - (pow(x, 2) + pow(y, 2) + x * y) pow(z, 2) +  y * z + z * x:
                    ans += 1
    print(ans)
Problem p02641 (python)

Fixed submission:
x, n = map(int, input().split())
p = list(map(int, input().split()))

if n == 0:
    print(x)
    exit()

p.sort()

if x not in p:
    print(x)
    exit()
    
for i in range(len(p)):
    #print(p[i])
    if p[i] == x:
        index = i
        break

right = x + 1
for i in p[index + 1:]:
    if i != right:
        break
    right += 1

left = x - 1
for i in reversed(p[:index]):
    if i != left:
        break
    left -= 1

if x - left <= right - x:
    print(left)
else:
    print(right)

Buggy submission (verdict: Runtime Error):
x, n = map(int, input().split())
p = list(map(int, input().split()))

if n == 0:
    print(x)
    exit()

p.sort()
#print(p)
for i in range(n):
    if p[i] == x:
        index = i
        break

right = x + 1
for i in p[index + 1:]:
    #print(i)
    if i != right:
        #print('aaaa')
        #print(right)
        break
    right += 1

left = x - 1
for i in reversed(p[:index]):
    #print(i)
    if i != left:
        #print('bbbb')
        #print(left)
        break
    left -= 1

if x - left <= right - x:
    print(left)
else:
    print(right)

Buggy submission (verdict: Runtime Error):
x, n = map(int, input().split())
p = list(map(int, input().split()))

if n == 0:
    print(x)
    exit()

p.sort()
print(p)
for i in range(n):
    if p[i] == x:
        index = i
        break

right = x + 1
for i in p[index + 1:]:
    print(i)
    if i != right:
        print('aaaa')
        print(right)
        break
    right += 1

left = x - 1
for i in reversed(p[:index]):
    print(i)
    if i != left:
        print('bbbb')
        print(left)
        break
    left -= 1

if x - left <= right - x:
    print(left)
else:
    print(right)
Problem p02714 (python)

Fixed submission:
n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(n):
    for d in range(1, n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(n):
    for d in range(1, n):
        j = i + d
        k = j + d
        if k > n:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

print(ans)
Problem p02756 (python)

Fixed submission:
from collections import deque
s = input()
Q = int(input())
que = deque(s)
cnt = 0
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        cnt += 1
    else:
        reverse = cnt % 2
        if q[1] == '1':
            if reverse == 0:
                s = que.appendleft(q[2])
            else:
                s = que.append(q[2])
        else:
            if reverse == 0:
                s = que.append(q[2])
            else:
                s = que.appendleft(q[2])

ans = ''.join(que)
if cnt % 2 == 0:
    print(ans)
else:
    print(ans[::-1])

Buggy submission (verdict: Runtime Error):
s = input()
Q = int(input())
query = [input().split() for _ in range(Q)]

cnt = 0
for q in query:
    if q[0] == '1':
        cnt += 1
    else:
        reverse = cnt % 2
        if q[1] == '1':
            if reverse == 0:
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if reverse == 0:
                s = s + q[2]
            else:
                s = q[2] + s
    print(s)
if cnt % 2 == 0:
    print(s)
else:
    print(s[::-1])
Problem p03246 (python)

Fixed submission:
n = int(input())
v = list(map(int, input().split()))
odd = {}
even = {}
change = 0
for i in range(n):
    if i % 2 == 0:
        if v[i] in even:
            even[v[i]] += 1
        else:
            even[v[i]] = 1
    else:
        if v[i] in odd:
            odd[v[i]] += 1
        else:
            odd[v[i]] = 1

if len(odd) == 1 and len(even) == 1:
    if odd == even:
        change = int(n / 2)
else:
    max_e = max(even, key=even.get)
    max_o = max(odd, key=odd.get)
    if max_e != max_o:
        change = n - even[max_e] - odd[max_o]
    else:
        if even[max_e] > even[max_o]:
            max_o2 = min(odd, key=odd.get)
            for o in odd:
                if o != max_o and odd[o] > odd[max_o2]:
                    max_o2 = o
            change = n - even[max_e] - odd[max_o2]
        elif even[max_e] == even[max_o]:
            max_o2 = min(odd, key=odd.get)
            for o in odd:
                if o != max_o and odd[o] > odd[max_o2]:
                    max_o2 = o
            max_e2 = min(even, key=even.get)
            for e in even:
                if e != max_e and even[e] > even[max_e2]:
                    max_e2 = e
            change = min(n - even[max_e] - odd[max_o2], n - odd[max_o] - even[max_e2])
        else:
            max_e2 = min(even, key=even.get)
            for e in even:
                if e != max_e and even[e] > even[max_e2]:
                    max_e2 = e
            change = n - odd[max_o] - even[max_e2]
print(change)

Buggy submission (verdict: Runtime Error):
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
c1 = Counter(v[::2])
c2 = Counter(v[1::2])
s1 = sorted(c1.items(), key=lambda x: x[1], reverse=True)
s2 = sorted(c2.items(), key=lambda x: x[1], reverse=True)

if len(s1) == 1 and len(s2) == 1:
    if s1[0][0] == s2[0][0]:
        ans = int(n / 2)
    else:
        ans = 0
else:
    if s1[0][0] != s2[0][0]:
        ans = n - s1[0][1] - s2[0][1]
    else:
        if s[0][1] > s2[0][1]:
            ans = n - s[0][1] - s[1][1]
        elif s[0][1] < s2[0][1]:
            ans = n - s[1][1] - s[0][1]
        else:
            ans = min(n - s[0][1] - s[1][1], n - s[1][1] - s[0][1])
print(ans)
Problem p02586 (python)

Fixed submission:
import io
import os
from collections import defaultdict

DEBUG = False
if not DEBUG:

    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    R, C, K = [int(x) for x in input().split()]
    grid = [[0 for c in range(C)] for r in range(R)]
    for r, c, v in ((int(x) for x in input().split()) for i in range(K)):
        grid[r - 1][c - 1] = v
else:
    import random

    random.seed(0)
    R, C = 3000, 3000
    # 2 * 10**5 / 90 * 10**5 full
    grid = [
        [int(random.randint(1, 90) <= 2) * random.randint(0, 10 ** 9) for c in range(C)]
        for r in range(R)
    ]
    print(sum(bool(grid[r][c]) for r in range(R) for c in range(C)))
    print("done gen")

    from timeit import default_timer as timer

    startTime = timer()


currRow = [[0 for i in range(3 + 1)] for c in range(C + 1)]
prevRow = [0 for c in range(C + 1)]
nextPrevRow = [0 for c in range(C + 1)]

inf = float("inf")
for r in range(R):
    for c in range(C):
        for numTakenThisRow in range(3 + 1):
            best = max(
                currRow[c - 1][numTakenThisRow],  # came from left
                prevRow[c],  # came from top, didn't take curr
                currRow[c - 1][numTakenThisRow - 1] + grid[r][c]
                if numTakenThisRow
                else 0,  # came from left, took curr
                prevRow[c] + grid[r][c]
                if numTakenThisRow == 1
                else 0,  # came from top, took curr
            )
            currRow[c][numTakenThisRow] = best
        nextPrevRow[c] = max(currRow[c][i] for i in range(3 + 1))
    prevRow, nextPrevRow = nextPrevRow, prevRow
print(prevRow[C - 1])

if DEBUG:
    print(timer() - startTime)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

# This TLEs, just checking correctness

R, C, K = [int(x) for x in input().split()]
grid = [[0 for c in range(C)] for r in range(R)]
for r, c, v in [[int(x) for x in input().split()] for i in range(K)]:
    grid[r - 1][c - 1] = v

# for row in grid:
#    print(row)


def best3(r, c1, c2):  # c1 inclusive, c2 exclusive
    return sum(sorted(grid[r][c1:c2], reverse=True)[:3])


@lru_cache(maxsize=None)
def dp(r, c):  # inclusive
    if r < 0 or c < 0:
        return 0
    best = 0
    for c1 in range(c + 1):
        best = max(best, dp(r - 1, c1) + best3(r, c1, c + 1))
    return best


print(dp(R - 1, C - 1))
Problem p02665 (python)

Fixed submission:
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

numLeafs = A
minNonLeafs = [None for i in range(N + 1)]
maxNonLeafs = [None for i in range(N + 1)]

maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]

minNonLeafs[N] = 0
maxNonLeafs[N] = 0
if minNonLeafs[N] + numLeafs[N] > 2 ** N:
    print(-1)
    exit()

for i in range(N - 1, -1, -1):
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])
    if minNonLeafs[i] > maxNonLeafs[i]:
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Buggy submission (verdict: Runtime Error):
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

numLeafs = A
minNonLeafs = [None for i in range(N + 1)]
maxNonLeafs = [None for i in range(N + 1)]

maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]

minNonLeafs[N] = 0
maxNonLeafs[N] = 0
if minNonLeafs[N] + numLeafs[N] > 2 ** N:
    print(-1)
    exit()

for i in range(N - 1, -1, -1):
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])
    if minNonLeafs[i] > maxNonLeafs[i]:
        assert False # TODO: do i need this case?
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)
Problem p02709 (python)

Fixed submission:
import sys

sys.setrecursionlimit(2 * 10 ** 5)

N = int(input())

A = [int(x) for x in input().split()]
A = sorted((a, i) for i, a in enumerate(A))

cache = [[None for i in range(N + 1)] for j in range(N + 1)]


def dp(l, r):
    if l > r:
        return 0
    if cache[l][r] is None:
        a, x = A[r - l]
        cache[l][r] = max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))
    return cache[l][r]


print(dp(0, N - 1))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

N = int(input())

A = [int(x) for x in input().split()]
A = sorted((a, i) for i, a in enumerate(A))


@lru_cache(maxsize=None)
def dp(l, r):
    if l > r:
        return 0
    a, x = A[r - l]
    return max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))


print(dp(0, N - 1))
Problem p02710 (python)

Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(2 * 10 ** 5)

(N,) = [int(x) for x in input().split()]
colors = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
parent = {1: None}
children = defaultdict(list)


def rootTree(node):
    for nbr in graph[node]:
        if nbr not in parent:
            parent[nbr] = node
            children[node].append(nbr)
            rootTree(nbr)


rootTree(1)


colorlessCount = [0 for c in range(N + 1)]
colorlessTime = [0 for c in range(N + 1)]
t = 0


def buildComps(node):
    global t
    t += 1
    currColor = colors[node - 1]
    colorlessTime[currColor] += 1
    for child in children[node]:
        oldCount = t - colorlessTime[currColor]
        colorlessTime[currColor] = t
        buildComps(child)
        s = t - colorlessTime[currColor]
        colorlessTime[currColor] = t - oldCount
        colorlessCount[currColor] += s * (s + 1) // 2


buildComps(1)

for c in range(1, N + 1):
    s = t - colorlessTime[c]
    colorlessCount[c] += s * (s + 1) // 2
maxPairs = N * (N + 1) // 2
for c in range(1, N + 1):
    print(maxPairs - colorlessCount[c])

Buggy submission (verdict: Runtime Error):
import sys
from collections import Counter, defaultdict, deque

# sys.setrecursionlimit(2 * 10 ** 5)

(N,) = [int(x) for x in input().split()]
colors = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
parent = {1: None}
children = defaultdict(list)


def rootTree(node):
    for nbr in graph[node]:
        if nbr not in parent:
            parent[nbr] = node
            children[node].append(nbr)
            rootTree(nbr)


rootTree(1)


colorlessCount = defaultdict(int)
colorlessTime = defaultdict(int)
t = 0
for c in range(1, N + 1):
    colorlessTime[c] = 0


def buildComps(node):
    global t
    t += 1
    currColor = colors[node - 1]
    colorlessTime[currColor] += 1
    for child in children[node]:
        oldCount = t - colorlessTime[currColor]
        colorlessTime[currColor] = t
        buildComps(child)
        s = t - colorlessTime[currColor]
        colorlessTime[currColor] = t - oldCount
        colorlessCount[currColor] += s * (s + 1) // 2


buildComps(1)
# print(colorToComps)
for c in colorlessTime:
    s = t - colorlessTime[c]
    colorlessCount[c] += s * (s + 1) // 2
maxPairs = N * (N + 1) // 2
for c in range(1, N + 1):
    print(maxPairs - colorlessCount[c])
Problem p02727 (python)

Fixed submission:
from functools import lru_cache

X, Y, A, B, C = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]
R = [int(x) for x in input().split()]

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

red = P[:X]
green = Q[:Y]
best = sum(red) + sum(green)

for x in R:
    a1, a2 = red, green
    if not a1 and not a2:
        break
    if not a1:
        a1 = a2
    if a1 and a2 and a1[-1] > a2[-1]:
        a1, a2 = a2, a1
    if a1[-1] < x:
        best -= a1.pop()
        best += x
print(best)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

X, Y, A, B, C = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]
R = [int(x) for x in input().split()]

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

red = P[:X]
green = Q[:Y]
best = sum(red) + sum(green)

for x in R:
    a1, a2 = red, green
    if a1[-1] > a2[-1]:
        a1, a2 = a2, a1
    assert a1[-1] <= a2[-1]
    if a1[-1] < x:
        best -= a1.pop()
        best += x
print(best)
Problem p02745 (python)

Fixed submission:
from itertools import permutations

ABC = [input().rstrip(), input().rstrip(), input().rstrip()]

cache = [-1] * (3 * 3)


def canMatchShifted(index1, index2, shift):
    # Whether ABC[index1] can match with ABC[index2] shifted to the right by `shift`
    k = 3 * index1 + index2
    if cache[k] == -1:
        S1 = ABC[index1]
        S2 = ABC[index2]
        temp = [True] * (4001)
        for s in range(len(S1)):
            temp[s] = all(x == y or x == "?" or y == "?" for x, y in zip(S1[s:], S2))
        cache[k] = temp

    return cache[k][shift]


# Try all permutation orders of ABC
best = float("inf")
for a, b, c in permutations(range(3)):
    A = ABC[a]
    B = ABC[b]
    C = ABC[c]
    # Match A with `('?' * i) + B`
    for i in range(2001):
        if not canMatchShifted(a, b, i):
            continue
        # Match B with `('?' * j) + C`
        # Match A with `('?' * (i + j)) + C`
        for j in range(2001):
            if canMatchShifted(b, c, j) and canMatchShifted(a, c, i + j):
                l = max(len(A), i + len(B), i + j + len(C))
                best = min(best, l)
print(best)

Buggy submission (verdict: Runtime Error):
from itertools import permutations

ABC = [input().rstrip(), input().rstrip(), input().rstrip()]

cache = [-1] * (3 * 3)


def canMatchShifted(index1, index2, shift):
    # Whether ABC[index1] can match with ABC[index2] shifted to the right by `shift`
    k = 3 * index1 + index2
    if cache[k] == -1:
        S1 = ABC[index1]
        S2 = ABC[index2]
        temp = [True] * (4001)
        for s in range(len(S1)):
            temp[s] = all(x == y or x == "?" or y == "?" for x, y in zip(S1[s:], S2))
        cache[k] = temp

    return cache[k][shift]


# Try all permutation orders of ABC
best = float("inf")
for a, b, c in permutations(range(3)):
    A = ABC[a]
    B = ABC[b]
    C = ABC[c]
    # Match A with `('?' * i) + B`
    for i in range(len(A) + 2):
        if not canMatchShifted(a, b, i):
            continue
        # Match B with `('?' * j) + C`
        # Match A with `('?' * (i + j)) + C`
        for j in range(len(B) + 2):
            if canMatchShifted(b, c, j) and canMatchShifted(a, c, i + j):
                l = max(len(A), i + len(B), i + j + len(C))
                best = min(best, l)
print(best)