Problem:


Score : 500 points

Problem Statement

Snuke has a string s.
From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c.
Find the minimum possible length of s.

Constraints

1 \leq |a|, |b|, |c| \leq 2000

a, b, and c consists of lowercase English letters and ?s.

Input

Input is given from Standard Input in the following format:

a
b
c

Output

Print the minimum possible length of s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.



Sample input:
a?c
der
cod


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
def connection(a, b, la, lb):
    #bがaの左にあるとき
    e = [b+a]
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        dic = {} # 文字変更候補のdict
        for j in range(i): # a[j] を調べる
            if a[j] == '?':
                if b[-i+j] != '?':
                    dic[j] = b[-i+j]
            elif a[j] != b[-i+j] and b[-i+j] != '?':
                break
            if j == i - 1:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(b[:lb-i] + d)
                f.append(la+lb-i)

    #bがaの右にあるとき
    e.append(a+b)
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        dic = {} # 文字変更候補のdict
        for j in range(1, i+1): # a[-j] を調べる
            if a[-j] == '?':
                if b[i-j] != '?':
                    dic[-j] = b[i-j]
            elif a[-j] != b[i-j] and b[i-j] != '?':
                break
            if j == i:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(d + b[i:])
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # a[i]から重なる
        dic = {}
        for j in range(lb):
            if a[i+j] == '?':
                if b[j] != '?':
                    dic[i+j] = b[j]
            elif a[i+j] != b[j] and b[j] != '?':
                break
            if j == lb - 1:
                d = a.copy()
                for k, l in dic.items():
                    d[k] = l
                e.append(d)
                f.append(la)

    return e, f
    #eはaとbを繋げたもののlist、fはその文字数


def connect(a, b, la, lb):
    #bがaの左にあるとき
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        for j in range(i): # a[j] を調べる
            if a[j] != b[-i+j] and b[-i+j] != '?' and a[j] != '?':
                break
            if j == i - 1:
                f.append(la + lb - i)

    #bがaの右にあるとき
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        for j in range(1, i+1): # a[-j] を調べる
            if a[-j] != b[i-j] and b[i-j] != '?' and a[-j] != '?':
                break
            if j == i:
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # a[i]から重なる
        for j in range(lb):
            if a[i+j] != b[j] and b[j] != '?' and a[i+j] != '?':
                break
            if j == lb - 1:
                f.append(la)

    return f
    #fは文字数


a = list(input())
b = list(input())
c = list(input())
la = len(a)
lb = len(b)
lc = len(c)

#最も長い文字列をaにする
if lb > la and lb >= lc:
    a, b = b, a
    la, lb = lb, la
elif lc > la and lc >= lb:
    a, c = c, a
    la, lc = lc, la

wc = [] #Word Count

e, f = connection(a, b, la, lb)
for i in range(len(e)):
    wc += connect(e[i], c, f[i], lc)

e, f = connection(a, c, la, lc)
for i in range(len(e)):
    wc += connect(e[i], b, f[i], lb)

print(min(wc))

Submission status: Time Limit Exceeded

Solution code:
def connection(a, b, la, lb):
    #bがaの左にあるとき
    e = [b+a]
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        d = a.copy()
        for j in range(i): # d[j] を調べる
            if d[j] == '?':
                d[j] = b[-i+j]
            elif d[j] != b[-i+j] and b[-i+j] != '?':
                break
            if j == i - 1:
                e.append(b[:lb-i] + d)
                f.append(la+lb-i)

    #bがaの右にあるとき
    e.append(a+b)
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        d = a.copy()
        for j in range(1, i+1): # d[-j] を調べる
            if d[-j] == '?':
                d[-j] = b[i-j]
            elif d[-j] != b[i-j] and b[i-j] != '?':
                break
            if j == i:
                e.append(d + b[i:])
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # d[i]から重なる
        d = a.copy()
        for j in range(lb):
            if d[i+j] == '?':
                d[i+j] = b[j]
            elif d[i+j] != b[j] and b[j] != '?':
                break
            if j == lb - 1:
                e.append(d)
                f.append(la)

    return e, f

    #eはaとbを繋げたもののlist、fはその文字数


def connect(a, b, la, lb):
    #bがaの左にあるとき
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        for j in range(i): # a[j] を調べる
            if a[j] != b[-i+j] and b[-i+j] != '?' and a[j] != '?':
                break
            if j == i - 1:
                f.append(la + lb - i)

    #bがaの右にあるとき
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        for j in range(1, i+1): # a[-j] を調べる
            if a[-j] != b[i-j] and b[i-j] != '?' and a[-j] != '?':
                break
            if j == i:
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # a[i]から重なる
        for j in range(lb):
            if a[i+j] != b[j] and b[j] != '?' and a[i+j] != '?':
                break
            if j == lb - 1:
                f.append(la)

    return f

    #eはaとbを繋げたもののlist、fはその文字数


a = list(input())
b = list(input())
c = list(input())
la = len(a)
lb = len(b)
lc = len(c)

#最も長い文字列をaにする
if lb > la and lb >= lc:
    a, b = b, a
    la, lb = lb, la
elif lc > la and lc >= lb:
    a, c = c, a
    la, lc = lc, la

wc = [] #Word Count

e, f = connection(a, b, la, lb)
for i in range(len(e)):
    wc += connect(e[i], c, f[i], lc)

e, f = connection(a, c, la, lc)
for i in range(len(e)):
    wc += connect(e[i], b, f[i], lb)

print(min(wc))

Submission status: Time Limit Exceeded

Solution code:
def connection(a, b, la, lb):
    #bがaの左にあるとき
    e = [b+a]
    f = [la+lb]
    for i in range(1, lb): # i = 重なる文字数
        d = a.copy()
        for j in range(i): # d[j] を調べる
            if d[j] == '?':
                d[j] = b[-i+j]
            elif d[j] != b[-i+j] and b[-i+j] != '?':
                break
            if j == i - 1:
                e.append(b[:lb-i] + d)
                f.append(la+lb-i)

    #bがaの右にあるとき
    e.append(a+b)
    f.append(la+lb)
    for i in range(1, lb): # i = 重なる文字数
        d = a.copy()
        for j in range(1, i+1): # d[-j] を調べる
            if d[-j] == '?':
                d[-j] = b[i-j]
            elif d[-j] != b[i-j] and b[i-j] != '?':
                break
            if j == i:
                e.append(d + b[i:])
                f.append(la + lb - i)

    #bがaの中にあるとき
    for i in range(la-lb+1): # d[i]から重なる
        d = a.copy()
        for j in range(lb):
            if d[i+j] == '?':
                d[i+j] = b[j]
            elif d[i+j] != b[j] and b[j] != '?':
                break
            if j == lb - 1:
                e.append(d)
                f.append(la)

    return e, f

    #eはaとbを繋げたもののlist、fはその文字数

a = list(input())
b = list(input())
c = list(input())
la = len(a)
lb = len(b)
lc = len(c)

#最も長い文字列をaにする
if lb > la and lb >= lc:
    a, b = b, a
    la, lb = lb, la
elif lc > la and lc >= lb:
    a, c = c, a
    la, lc = lc, la

res = [] #sの候補
wc = [] #Word Count

e, f = connection(a, b, la, lb)
for i in range(len(e)):
    g, h = connection(e[i], c, f[i], lc)
    res.append(g)
    wc += h

e, f = connection(a, c, la, lc)
for i in range(len(e)):
    g, h = connection(e[i], b, f[i], lb)
    res.append(g)
    wc += h

print(min(wc))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, permutations


def matches(x, y):
    return x == '?' or y == '?' or x == y


def is_stackable(str_fixed, str_moving, gap):
    for j in range(len(str_moving)):
        if gap + j >= len(str_fixed):
            return True
        if not matches(str_fixed[gap + j], str_moving[j]):
            return False
    return True


def solve(a, b, c):
    stackables = [[True for _ in range(4001)] for _ in range(3)]
    for i, (x, y) in enumerate(combinations((a, b, c), 2)):
        for j in range(len(x)):
            stackables[i][j] = is_stackable(x, y, j)

    res = len(a + b + c)
    for i in range(len(a) + 1):
        for j in range(max(len(b) + 1, len(a) - i + 1)):
            if stackables[0][i] and stackables[1][i + j] and stackables[2][j]:
                res = min(res, max(len(a), i + len(b), i + j + len(c)))
    return res


if __name__ == "__main__":
    str_a = input()
    str_b = input()
    str_c = input()

    print(min([solve(a, b, c) for a, b, c in permutations((str_a, str_b, str_c))]))

Submission status: Time Limit Exceeded

Solution code:
a=input()
b=input()
c=input()

X=[a,b,c]
LEN=[len(a),len(b),len(c)]

MF=[[[1]*2001 for j in range(3)] for i in range(3)]

for i in range(3):
    for j in range(3):
        if i==j:
            continue
        for k in range(2001):
            for l in range(LEN[j]):
                if k+l>=LEN[i]:
                    break
                if X[i][k+l]!="?" and X[j][l]!="?" and X[i][k+l]!=X[j][l]:
                    MF[i][j][k]=0
                    break

ANS=1000000
for i in range(3):
    for j in range(3):
        if i==j:
            continue
        for k in range(2001):
            if MF[i][j][k]==1:
                for l in range(2001):
                    if ANS<=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l):
                        break
                    if MF[j][3-i-j][l]==1 and (k+l>2000 or MF[i][3-i-j][k+l]==1):
                        ANS=max(LEN[i],LEN[j]+k,LEN[3-i-j]+k+l)

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
K=4000
R=range
y=min
l=len
A,B,C=[input()for i in R(3)]
def F(a,b):
 Q=[1]*(K*2+1)
 for i in R(-l(b),l(a)):
  for j in R(max(i,0),y(l(a),l(b)+i)):
   if l(set([a[j],b[j-i],'?']))>2:Q[i]=0
 return Q
S=F(A,B)
T=F(A,C)
m=K*3
k=R(-K,K+1)
for p in k:
 if S[p]!=0:
  for q in k:
   if T[q]!=0 and F(B,C)[q-p]!=0:m=y(m,max(p+l(B),q+l(C),l(A))-y(p,q,0))
print(m)

Submission status: Time Limit Exceeded

Solution code:
K=4000
R=range
y=min
l=len
S=[input()for i in R(3)]
A,B,C=S
a,b,c=[l(i)for i in S]
def F(S,T):
 Q=[1]*(K*2+1)
 for i in R(-l(T),l(S)):
  for j in R(max(i,0),y(l(S),l(T)+i)):
   if l(set([S[j],T[j-i],'?']))>2:Q[i]=0
 return Q
m=K*3
k=R(-K,K+1)
for p in k:
 if F(A,B)[p]!=0:
  for q in k:
   if F(A,C)[q]!=0 and F(B,C)[q-p]!=0:m=y(m,max(p+b,q+c,a)-y(p,q,0))
print(m)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

# 二つの文字列の場合を考える。
# 二つの文字列を生み出せるような最小の文字列を求める関数。
# print(a,b,c)

#文字列sとtが等しいか判定する関数。(?込)
def equal(s,t):
    #sとtは同じ長さ。
    l = len(s)
    for i in range(l):
        if s[i] != t[i] and s[i] != "?" and t[i] != "?":
            return False
            break
    return True
    
def merge(s,t):
    #sとtは同じ長さ。
    u = ""
    l = len(s)
    for i in range(l):
        if s[i] == "?":
            if t[i] == "?":
                u += "?"
            else:
                u += t[i]
        else:
            u += s[i]
    return u


def sub_2(a0,b0):
    Y0 = []
    # a>=bとする。
    if len(a0) >= len(b0):
        a,b=a0,b0
    else:
        a,b=b0,a0
    
    # aがbを含む場合。
    for i in range(len(a)-len(b)+1):
        # print(a[i:i+len(b)])
        if equal(a[i:i+len(b)],b):
            # print(a,b,[a[:i] + merge(a[i:i+len(b)],b) + a[i+len(b):]])
            Y0.append(a[:i] + merge(a[i:i+len(b)],b) + a[i+len(b):])
    
    # aの右がbの左と重なる場合。
    for i in range(len(b)-1):
        # print(a[-len(b)+i+1:],b[:-i-1])
        if equal(a[-len(b)+i+1:],b[:-i-1]):
            Y0.append(a[:-len(b)+i+1] + merge(a[-len(b)+i+1:],b[:-i-1]) + b[-i-1:])
    
    # aの左がbの右と重なる場合。
    for i in range(len(b)-1):
        # print(b[i+1:],a[:len(b)-i-1])
        if equal(b[i+1:],a[:len(b)-i-1]):
            Y0.append(b[:i+1] + merge(b[i+1:],a[:len(b)-i-1]) + a[len(b)-i-1:])
    
    if not Y0:
        return [a+b,b+a]
    else:
        return Y0


Y = []
for i in sub_2(a,b):
    # print(i,c,1)
    for j in sub_2(i,c):
        # print(j)
        Y.append(len(j))
"""
for i in sub_2(b,c):
    # print(i,a,2)
    for j in sub_2(i,a):
        Y.append(len(j))
        # print(j)
"""
for i in sub_2(c,a):
    # print(i,b,3)
    for j in sub_2(i,b):
        Y.append(len(j))
        # print(j)

# print(Y)
print(min(Y))

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

# 二つの文字列の場合を考える。
# 二つの文字列を生み出せるような最小の文字列を求める関数。
# print(a,b,c)

#文字列sとtが等しいか判定する関数。(?込)
def equal(s,t):
    #sとtは同じ長さ。
    l = len(s)
    for i in range(l):
        if s[i] != t[i] and s[i] != "?" and t[i] != "?":
            return False
            break
    return True
    
def merge(s,t):
    #sとtは同じ長さ。
    u = ""
    l = len(s)
    for i in range(l):
        if s[i] == "?":
            if t[i] == "?":
                u += "?"
            else:
                u += t[i]
        else:
            u += s[i]
    return u


def sub_2(a0,b0):
    Y0 = []
    # a>=bとする。
    if len(a0) >= len(b0):
        a,b=a0,b0
    else:
        a,b=b0,a0
    
    # aがbを含む場合。
    for i in range(len(a)-len(b)+1):
        # print(a[i:i+len(b)])
        if equal(a[i:i+len(b)],b):
            # print(a,b,[a[:i] + merge(a[i:i+len(b)],b) + a[i+len(b):]])
            Y0.append(a[:i] + merge(a[i:i+len(b)],b) + a[i+len(b):])
    
    # aの右がbの左と重なる場合。
    for i in range(len(b)-1):
        # print(a[-len(b)+i+1:],b[:-i-1])
        if equal(a[-len(b)+i+1:],b[:-i-1]):
            Y0.append(a[:-len(b)+i+1] + merge(a[-len(b)+i+1:],b[:-i-1]) + b[-i-1:])
    
    # aの左がbの右と重なる場合。
    for i in range(len(b)-1):
        # print(b[i+1:],a[:len(b)-i-1])
        if equal(b[i+1:],a[:len(b)-i-1]):
            Y0.append(b[:i+1] + merge(b[i+1:],a[:len(b)-i-1]) + a[len(b)-i-1:])
    
    if not Y0:
        return [a+b,b+a]
    else:
        return Y0


Y = []
for i in sub_2(a,b):
    # print(i,c,1)
    for j in sub_2(i,c):
        # print(j)
        Y.append(len(j))
for i in sub_2(b,c):
    # print(i,a,2)
    for j in sub_2(i,a):
        Y.append(len(j))
        # print(j)
for i in sub_2(c,a):
    # print(i,b,3)
    for j in sub_2(i,b):
        Y.append(len(j))
        # print(j)

# print(Y)
print(min(Y))

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()
def func(a, b):
    ret = set()
    for i in range(-len(b)+1, len(a)):
        ok = True
        for j in range(max(0, i), min(len(a), len(b)+i)):
            if a[j] != '?' and b[j-i] != '?' and a[j] != b[j-i]:
                ok = False
                break
        if ok:
            ret.add(i)
    return ret
L1 = func(a, b)
L2 = func(a, c)
L3 = func(b, c)
L1.add(-len(b))
L1.add(len(a))
L2.add(-len(c))
L2.add(len(a))
L3.add(-len(c))
L3.add(len(b))
ans = 10000
for i in L1:
    for j in L2:
        if j - i in L3 or j - i <= -len(c) or j - i >= len(b):
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    for k in L3:
        j = i + k
        if j >= len(a) or j <= -len(c):
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
for j in L2:
    for k in L3:
        i = j - k
        if i >= len(a) or i <= -len(b):
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

# 文字のマッチング(?はワイルドカード)
def match(a, b):
    return a=="?" or b=="?" or a==b

ab = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にBを置けるか？
ac = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にCを置けるか？
bc = [True] * 100000 # Bに対して(i-50000)個左にスライドした位置にCを置けるか？

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)

ans = len_a + len_b + len_c

# i = BをAに対していくつスライドして置くか
for i in range(-2 * len_max, 2 * len_max + 1):
    # j = CをAに対していくつスライドして置くか
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            size = right - left
            if size < ans:
                ans = size

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [True] * 16000, [True] * 16000, [True] * 16000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] != '?' and a[i] != b[j]:
            ab[i-j+8000]= False
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and b[i] != c[j]:
            bc[i-j+8000]= False
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and a[i] != c[j]:
            ac[i-j+8000]= False
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [True] * 20000, [True] * 20000, [True] * 20000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+10000]= False
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+10000]= False
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+10000]= False
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 20000, [1] * 20000, [1] * 20000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+10000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+10000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+10000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+6000]= 0
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+6000]= 0
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+6000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 20000, [1] * 20000, [1] * 20000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+10000]= 0
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000]= 0
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+10000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+10000] and bc[j-i+10000] and ac[j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ca = [1] * 20000, [1] * 20000, [1] * 20000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+10000]= 0
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000]= 0
for i in range(C):
    for j in range(A):
        if not match(c[i], a[j]):
            ca[i-j+10000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+10000] and bc[j-i+10000] and ca[-j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ca = [True] * 20000, [True] * 20000, [True] * 20000

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i - j + 10000]= False
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i - j + 10000]= False
for i in range(C):
    for j in range(A):
        if not match(c[i], a[j]):
            ca[i - j + 10000]= False
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i + 10000] and bc[j-i+10000] and ca[-j+10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    Sss = [input().rstrip() for _ in range(3)]

    Sss.sort(key=len, reverse=True)
    As, Bs, Cs = Sss
    lenA, lenB, lenC = len(As), len(Bs), len(Cs)

    def check(Ss, Ts):
        for S, T in zip(Ss, Ts):
            if not (S == T or S == '?' or T == '?'):
                return 0
        return 1

    def getISOKs(Ss, Ts):
        lenS, lenT = len(Ss), len(Ts)
        isOKs = [0] * (lenS+lenT+1)
        for iT in range(-lenT, 0):
            isOKs[iT] = check(Ss[:lenT+iT], Ts[-iT:])
        for iT in range(0, lenS-lenT+1):
            isOKs[iT] = check(Ss[iT:lenT+iT], Ts)
        for iT in range(lenS-lenT+1, lenS+1):
            isOKs[iT] = check(Ss[iT:], Ts[:lenS-iT])
        return isOKs

    isOKABs = getISOKs(As, Bs)
    isOKACs = getISOKs(As, Cs)
    isOKBCs = getISOKs(Bs, Cs)
    isOKBCs = isOKBCs[:lenB+1] + [1]*(lenA+lenB+lenC) + isOKBCs[lenB+1:]

    ans = lenA + lenB + lenC
    for iB in range(-lenB, lenA+1):
        if not isOKABs[iB]: continue
        for iC in range(-lenC, lenA+1):
            if isOKACs[iC] and isOKBCs[iC-iB]:
                L = max(lenA, iB+lenB, iC+lenC) - min(0, iB, iC)
                ans = min(ans, L)
    for iB in range(-lenB, lenA+1):
        if not isOKABs[iB]: continue
        for iC in range(-lenB-lenC, -lenC+1):
            if isOKBCs[iC-iB]:
                L = max(lenA, iB+lenB, iC+lenC) - min(0, iB, iC)
                ans = min(ans, L)
        for iC in range(lenA, lenA+lenB+1):
            if isOKBCs[iC-iB]:
                L = max(lenA, iB+lenB, iC+lenC) - min(0, iB, iC)
                ans = min(ans, L)
    for iC in range(-lenC, lenA+1):
        if not isOKACs[iC]: continue
        for iB in range(-lenB-lenC, -lenB+1):
            if isOKBCs[iC-iB]:
                L = max(lenA, iB+lenB, iC+lenC) - min(0, iB, iC)
                ans = min(ans, L)
        for iB in range(lenA, lenA+lenB+1):
            if isOKBCs[iC-iB]:
                L = max(lenA, iB+lenB, iC+lenC) - min(0, iB, iC)
                ans = min(ans, L)

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-9000, 9001)}
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ac[c_idx] and check_bc[c_idx - b_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-10000, 10001)}
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ac[c_idx] and check_bc[c_idx - b_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-10000, 10001)}
    for i in range(len(s)):
        for j in range(len(t)):
            if not comp(s[i], t[j]):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ac[c_idx] and check_bc[c_idx - b_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == '?' or c2 == '?' or c1 == c2

M = 2000

ab, ac, bc = [], [], []
for _  in range(10000):
    ab.append(0)
    ac.append(0)
    bc.append(0)

for _  in range(10000):
    bc.append(0)

A, B, C = len(a), len(b), len(c)
for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+5000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+5000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000] = 1

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == '?' or c2 == '?' or c1 == c2

M = 2000

ab = [0 for _  in range(10000)]
ac = [0 for _  in range(10000)]
bc= [0 for _  in range(20000)]

A, B, C = len(a), len(b), len(c)
for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+5000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+5000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000] = 1

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def fit(a: str, b: str, a_start: int, b_start: int):
    a_terminal = a_start + len(a)
    b_terminal = b_start + len(b)

    if b_terminal <= a_start or a_terminal <= b_start:
        return True

    max_start = max(a_start, b_start)
    min_terminal = min(a_terminal, b_terminal)

    if not all([a[i - a_start] == '?' or b[i - b_start] == '?' or a[i - a_start] == b[i - b_start]
                for i in range(max_start, min_terminal)]):
        return False

    return True


def main():
    a = input()
    b = input()
    c = input()

    min_s_len = 6000

    for b_start in range(-(len(b) + len(c)), len(a) + len(b) + len(c)):
        if not fit(a, b, 0, b_start):
            continue

        for c_start in range(-(len(b) + len(c)), len(a) + len(b) + len(c)):
            if (not fit(a, c, 0, c_start)) or (not fit(b, c, b_start, c_start)):
                continue

            s_len = max(len(a), b_start + len(b), c_start + len(c)) - min(0, b_start, c_start)
            min_s_len = min(s_len, min_s_len)

    print(min_s_len)


main()