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: Runtime Error

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for m, lr in merge2(a,b):
    yield m

def merge2(a,b,lr=None):
  for i in range(1,len(b)):
    if lr!=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], 1
    if lr!=1:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], 0
  yield a+b, 0
  yield b+a, 1

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d, lr in merge2(a,c):
  if len(d) > abc:
    break
  l = len(next(merge(d, b, lr)))
  abc = min(abc, l)
print(abc)

Submission status: Runtime Error

Solution code:
import copy
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            if self.P[i] == self.P[j]:
                j+=1
            elif self.P[i]=='?' or self.P[j]=='?':
                j+=1
            else:
                j=0
        self.T[self.N] = j
        #print(self.T)
      

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    zz=a+['?']*zn
    #r=len(a)
    kl=KMP(b).search(zz)
    ret=100000000
    for k in kl:
        z=zz[:] 
        for i in range(len(b)):
            if b[i]!='?':
                z[k+i]=b[i]
        #r=max(r,k+len(b))
        kl2=KMP(c).search(z)
        k2=min(kl2)
        ret=min(ret,max(k+len(b),k2+len(c),len(a)))
    #print(kl)
    #print(''.join(z))
    return ret
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Runtime Error

Solution code:
import copy
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            if self.P[i] == self.P[j]:
                j+=1
            elif self.P[i]=='?' or self.P[j]=='?':
                j+=1
            else:
                j=0
        self.T[self.N] = j
        #print(self.T)
      

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    zz=a+['?']*zn
    #r=len(a)
    kl=KMP(b).search(zz)
    ret=100000000
    for k in kl:
        z=copy.deepcopy(zz)    
        for i in range(len(b)):
            if b[i]!='?':
                z[k+i]=b[i]
        #r=max(r,k+len(b))
        kl2=KMP(c).search(z)
        k2=min(kl2)
        ret=min(ret,max(k+len(b),k2+len(c),len(a)))
    #print(kl)
    #print(''.join(z))
    return ret
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Runtime Error

Solution code:
import itertools, copy

a = input()
b = input()
c = input()

s = [a, b, c]
ans = 6000
for i in itertools.permutations(s):
    check = [None] * 6000
    temp1 = list(i[0])
    for j in range(len(temp1)):
        check[j] = temp1[j]
    for j in range(len(temp1) + 1):
        flag = True
        temp2 = list(i[1])
        check2 = copy.copy(check)
        for k in range(len(temp2)):
            if check2[j + k] == None or check2[j + k] == "?":
                check2[j + k] = temp2[k]
            elif check2[j + k] != temp2[k]:
                flag = False
                break
        if flag == False:
            continue
        else:
            for k in range(max(len(temp1), j + len(temp2)) + 1):
                temp3 = list(i[2])
                flag2 = True
                for l in range(len(temp3)):
                    if temp3[l] == "?":
                        continue
                    else:
                        if check2[k + l] == None or check2[k + l] == "?":
                            continue
                        elif check2[k + l] == temp3[l]:
                            continue
                        else:
                            flag2 = False
                            break
                if flag2 == False:
                    continue
                else
                    ans = min(ans, max(len(temp1), j + len(temp2), k + len(temp3)))
print(ans)

Submission status: Runtime Error

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            if self.P[i] == self.P[j]:
                j+=1
            elif self.P[i]=='?' or self.P[j]=='?':
                j+=1
            else:
                j=0
        self.T[self.N] = j
        #print(self.T)
      

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    zz=a+['?']*zn
    #r=len(a)
    kl=KMP(b).search(zz)
    ret=100000000
    for k in kl:
        z=zz     
        for i in range(len(b)):
            if b[i]!='?':
                z[k+i]=b[i]
        #r=max(r,k+len(b))
        kl2=KMP(c).search(z)
        k2=min(kl2)
        ret=min(ret,max(k+len(b),k2+len(c),len(a)))
    #print(kl)
    #print(''.join(z))
    return ret
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Runtime Error

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            if self.P[i] == self.P[j]:
                j+=1
            elif self.P[i]=='?' or self.P[j]=='?':
                j+=1
            else:
                j=0
        self.T[self.N] = j
        #print(self.T)
      

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i] or self.P[i]=='?' or S[m+i]=='?':#
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

a=list(input())
b=list(input())
c=list(input())
s=[a,b,c]
zn=len(a)+len(b)+len(c)
def solve(a,b,c):
    zz=a+['?']*zn
    #r=len(a)
    kl=KMP(b).search(z)
    ret=100000000
    for k in kl:
        z=zz     
        for i in range(len(b)):
            if b[i]!='?':
                z[k+i]=b[i]
        #r=max(r,k+len(b))
        kl2=KMP(c).search(z)
        k2=min(kl2)
        ret=min(ret,max(k+len(b),k2+len(c),len(a)))
    #print(kl)
    #print(''.join(z))
    return ret
ans=10**10
for i in range(3):
    for j in range(3):
        for k in range(3):
            if i==j or j==k or k==i:
                continue
            ans=min(ans,solve(s[i],s[j],s[k]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[chr(97+int(i)) for i in range(n)]

Ans=["a"]
if n>=2:
  for _ in range(n-1):
    Ans2=[]
    for a in Ans:
      s=set()
      for aa in a:
        s.add(aa)
      ss=len(s)
      for i in range(ss+1):
        Ans2.append(a+A[i])
    Ans=Ans2
Ans.sort()
for ans in Ans:
  print(ans)

Submission status: Runtime Error

Solution code:
maxn = 2000 * 3 + 3
maxnh = maxn // 2

def check(s, t, d):
    for i in range(max(0, d), min(len(s), len(t) + d)):
        if s[i] != '?' and t[i] != '?' and s[i] != t[i - d]:
            return False
    return True

def ca(s, t):
    res = [True] * maxn
    for i in range(-len(t), len(s) + 1):
        res[i + maxnh] = check(s, t, i)
    return res

a, b, c = (input() for _ in range(3))
ans = sum(map(len, (a, b, c)))
ab, bc, ac = ca(a, b), ca(b, c), ca(a, c)
for i in range(maxn):
    if not ab[i]:
        continue
    for j in range(maxn):
        if not bc[j]:
            continue
        if not (0 <= i + j - maxnh < maxn) or not ac[i + j - maxnh]:
            continue
        ans = min(ans, max(len(a), len(b) + i - maxnh, len(c) + i + j - maxnh * 2) - min(0, i - maxnh, i + j - maxnh * 2))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from itertools import permutations

A = input()
B = input()
C = input()

ans = len(A) + len(B) + len(C)

def merge(X, Y, offset=0):
  ret = deque()
  for i in range(offset, len(X)):
    s = deque(X[:i])
    for x, y in zip(X[i:], Y):
      if x == '?' or x == y:
        s.append(y)
      elif y == '?':
        s.append(x)
      else:
        break
    else:
      ret.append(s.extend(Y[len(X)-i:]))
  return ret

for X, Y, Z in permutations([A, B, C]):
  for W in merge(X, Y):
    if len(W) >= ans:
      break
    ans = min(ans, len(W) + len(Z))
    for E in merge(W, Z, len(W) - len(Y)):
      ans = min(ans, len(E))

print(ans)

Submission status: Runtime Error

Solution code:
import re

a = input()
b = input()
c = input()

_min = len(a) + len(b) + len(c)

def toreg(s):
    res = ''
    for c in s:
        if c == '?':
            res += '.'
        else:
            res += '[' + c + '?]'
    return res

def merge(s1, s2):
    m = re.search(toreg(s2), s1 + '?'*len(s2))
    if not m:
        return s1 + s2
    p = m.start()

    res = s1[:p]
    l = len(s1[p:])
    for i in range(l):
        if s1[p+i] == '?':
            res += s2[i]
        else:
            res += s1[p+i]
    res += s2[l:]
    return res

s = []
d = merge(a, b)
s.append(merge(c, d))
s.append(merge(d, c))
d = merge(a, c)
s.append(merge(b, d))
s.append(merge(d, b))
d = merge(b, a)
s.append(merge(c, d))
s.append(merge(d, c))
d = merge(b, c)
s.append(merge(a, d))
s.append(merge(d, a))
d = merge(c, a)
s.append(merge(b, d))
s.append(merge(d, b))
d = merge(c, b)
s.append(merge(a, d))
s.append(merge(d, a))

for _s in s:
    if len(_s) < _min:
        _min = len(_s)

print(_min)

Submission status: Runtime Error

Solution code:
from itertools import permutations
def match(a,b):
    nb = len(b)
    na = len(a)
    res=0
    for i in range(1,nb+1):
        for j in range(i):
            if not(a[na-i+j] == b[j] or a[na-i+j] == '?' or  b[j] == '?'):
                break
        else:
            res=max(res,i)
    return res


a = input()
b = input()
c = input()
stls = [a,b,c]
ans=1001001001

for ls in permutations(stls):
    ansstring = ls[0]
    idx = match(ansstring, ls[1])
    ansstring += ls[1][idx:]
    idx = match(ansstring, ls[2])
    ansstring += ls[2][idx:]
    ans=min(ans,len(ansstring))

print(ans)

Submission status: Runtime Error

Solution code:
import functools


def solve(a, b, c):
    ans = 6000
    # for line in get_merge_points(a, b, one_result=False):
    #     # print(line)
    #     ans = min(ans, list(get_merge_points(line, c, one_result=True))[0])
    # return ans
    for b_index in range(len(a) + 1):
        for c_index in range(b_index, b_index + len(b) + 1):
            if max(len(a), b_index + len(b), c_index + len(c)) > ans:
                break
            if check(a, b, c, b_index, c_index):
                ans = min(ans, max(len(a), b_index + len(b), c_index + len(c)))
                break

    return ans


def _check(a, b, c, b_index, c_index):
    # a and b
    for p in range(b_index, min(c_index, len(a), b_index + len(b))):
        if a[p] and b[p - b_index] and a[p] != b[p - b_index]:
            return False

    for p in range(c_index, min(b_index + len(b), c_index + len(c))):
        if c[p - c_index] and b[p - b_index] and c[p - c_index] != b[p - b_index]:
            return False

    for p in range(c_index, min(len(a), b_index + len(b), c_index + len(c))):
        if a[p] == b[p - b_index] == c[p - c_index] or (
                (a[p] == 0) + (b[p - b_index] == 0) + (c[p - c_index] == 0)) > 2:
            continue
        elif a[p] and b[p - b_index] and c[p - c_index] and (
                a[p] != b[p - b_index] or b[p - b_index] != c[p - c_index] or c[p - c_index] != a[p]):
            return False
        elif a[p] == b[p - b_index] or a[p] == c[p - c_index] or b[p - b_index] == c[p - c_index]:
            continue
        else:
            return False
    return True


def get_merge_points(base, ext, one_result=True):
    for point in range(len(base) + 1):
        flag = set()
        for i in range(point, min(len(base), point + len(ext))):
            if base[i] == ext[i - point]:
                '?? or aa'
                continue
            elif base[i] == 0 or ext[i - point] == 0:
                flag.add(i)
            else:
                break
        else:
            if one_result:
                yield max(len(base), point + len(ext))
                return
            if len(base) > point + len(ext):
                source = list(base)
            else:
                source = list(base[:point]) + list(ext)

            for f in flag:
                source[f] = base[f] if base[f] != 0 else ext[f - point]
            yield source


def convert(st):
    result = []
    for s in st:
        if s == '?':
            result.append(0)
        else:
            result.append(ord(s) - 90)
    return result


a = convert(input())
b = convert(input())
c = convert(input())


@functools.lru_cache(maxsize=None)
def check(base, target, x_index):
    if base == 1:
        z = b
    else:
        z = a
    if target == 1:
        x = b
    else:
        x = c
    for p in range(max(0, x_index), min(len(z), x_index + len(b))):
        if z[p] and x[p - x_index] and z[p] != x[p - x_index]:
            return False
    return True


t = len(a) + len(b) + len(c)
ans = t
for b_index in range(-t, min(2001, t)):
    if not check(base=0, target=1, x_index=b_index):
        continue
    for c_index in range(-t, min(2001, t)):
        left = min(b_index, c_index, 0)
        right = max(len(a), b_index + len(b), c_index + len(c))
        if ans <= right - left:
            continue
        if check(base=0, target=2, x_index=c_index) and check(base=1, target=2, x_index=c_index - b_index):
            ans = right - left
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)


def js(s1, s2):

    for i in range(0, len(s1)):
        flag = True
        for j in range(0, len(s1) - i):
            c1 = s1[i + j]
            c2 = s2[j]

            if c1 != '?' and c2 != '?' and c1 != c2:
                flag = False
                break

        if flag:
            return s1[:i] + s2
    return s1 + s2


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

    ac = js(a, c)
    ab = js(a, b)
    ba = js(b, a)
    bc = js(b, c)
    ca = js(c, a)
    cb = js(c, b)

    abc = js(ab, c)
    acb = js(ac, b)
    bac = js(ba, c)
    bca = js(bc, a)
    cab = js(ca, b)
    cba = js(cb, a)

    print(min(len(s) for s in (abc, acb, bac, bca, cab, cba)))


main()

Submission status: Runtime Error

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def cmp1(a,b):
    l = []
    for i in range(len(a)):
        ok = True
        for j in range(len(a)-i):
            #ddprint("a {} b {} i {} j {}".format(a,b,i,j))
            #ddprint("aij {} bj {}".format(a[i+j],b[j]))
            if a[i+j]!='?' and b[j]!='?' and a[i+j]!=b[j]:
                ok = False
                break
        if ok:
            l.append(i)
    #ddprint("cmp1 a {} b {} l {}".format(a,b,l))
    return l

def cmp(a,b):
    l1 = cmp1(a,b)
    l2 = cmp1(b,a)
    l2m = [-x for x in l2 if x!=0]
    l1.extend(l2m)
    return l1

a = ins()
b = ins()
c = ins()
la = len(a)
lb = len(b)
lc = len(c)
ab = cmp(a,b)
ac = cmp(a,c)
bc = cmp(b,c)
ddprint(ab)
ddprint(ac)
ddprint(bc)
ba = [-x for x in ab]
ca = [-x for x in ac]
cb = [-x for x in bc]
mn = la+lb+lc
for i in ab:
    for j in ac:
        if lc+j<=i or lb+i<=j or (j-i) in bc:
            v = max([la,lb+i,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ba:
    for j in bc:
        if lc+j<=i or la+i<=j or (j-i) in ac:
            v = max([la+i,lb,lc+j]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ca:
    for j in cb:
        if lb+j<=i or la+i<=j or (j-i) in ab:
            v = max([la+i,lb+j,lc]) + max(0,-i,-j)
            mn = min(mn,v)
ddprint(mn)
for i in ab:
    v = max(la,lb+i)+max(0,-i)+lc
    mn = min(mn,v)
ddprint(mn)
for i in ac:
    v = max(la,lc+i)+max(0,-i)+lb
    mn = min(mn,v)
ddprint(mn)
for i in bc:
    v = max(lb,lc+i)+max(0,-i)+la
    mn = min(mn,v)
print(mn)

Submission status: Runtime Error

Solution code:
import sys
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
c = sys.stdin.readline().strip()
def match(x, y):
    for i in range(len(x)):
        if x[i] != "?":
            if y[i] != "?":
                if x[i] != y[i]:
                    return False
    return True

def do(a,b,c):
    #print (a,b,c)
    res = ""
    # a b c
    for p in range(len(a)):
        if match(a[p:], b[:len(b)-p]):
            # merge the string
            res = a[:p]
            for j in range(len(b)-p):
                if a[j+p] != "?":
                    res += a[j+p]
                else:
                    res += b[j]
            res += b[-p:]
            break
    if res == "":
        res = a+b
    #print(res)
    a = res[len(res)-len(b):]
    before = len(res)-len(b)
    b = c
    #print(before)
    
    #print(a,b)
    for p in range(len(a)):
        if match(a[p:], b[:len(b)-p]):
            # merge the string
            return before + p + len(b)
    
    return 2*len(b) + before

tests = []
tests.append(do(a,b,c))
tests.append(do(a,c,b))
tests.append(do(b,a, c))
tests.append(do(b,c, a))
tests.append(do(c, b, a))
tests.append(do(c, a, b))
print(min(tests))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
l = []
def calc3(s, N):
    if len(s) == N:
        print(s)
        l.append(s)
        return
    if len(s) > 0:
        c = s[-1]
        s2 = s[:]
        z = ord(c) - ord('a') + 2
        for i in range(z):
            st = s[:]
            st += chr(ord('a')+i)
            calc3(st[:], N)
    else:
        c = 'a'
        s += chr(ord(c))
        calc3(s[:], N)
def main():
    N = int(input())
    s = ''
    calc3(s[:], N)
main()

Submission status: Runtime Error

Solution code:
def inner(a,b,la,lb):
  for i in range(lb-la+1):
    for j in range(la):
      if a[j]=='?' or a[j]==b[i+j]:
        continue
      elif b[i+j]=='?':
        continue
      else:
        break
    else:
      return True
  return False

def head(a,b,la):
  for i in range(la,-1,-1):
    for j in range(i):
      if a[j]=='?' or a[j]==b[-(i-j)]:
        continue
      elif b[-(i-j)]=='?':
        continue
      else:
        break
    else:
      return b+a[i:]

def tail(a,b,la):
  for i in range(la,-1,-1):
    for j in range(i):
      if a[-(i-j)]=='?' or a[-(i-j)]==b[j]:
        continue
      elif b[j]=='?':
        continue
      else:
        break
    else:
      return a+b[i:]
      break

a=input()
la=len(a)
b=input()
lb=len(b)
c=input()
lc=len(c)
arr=[[a,la],[b,lb],[c,lc]]
arr=sorted(arr,key=lambda x:x[1])
a,la=arr[0]
b,lb=arr[1]
c,lc=arr[2]
tmp1=head(a,c,la)
tmp2=tail(a,c,la)
ans1=min(len(head(b,tmp1,lb)),len(tail(b,tmp1,lb)))
if inner(b,tmp1,lb,len(tmp1)):
  ans1=min(ans1,len(tmp1))
ans2=min(len(head(b,tmp2,lb)),len(tail(b,tmp2,lb)))
if inner(b,tmp2,lb,len(tmp2)):
  ans2=min(ans2,len(tmp2))
ans3=10**18
if inner(a,c,la,lc):
  ans3=min(len(head(b,c,lb)),len(tail(b,c,lb)))
  if inner(b,c,lb,lc):
    ans3=min(ans3,lc)
ansac=min(ans1,ans2,ans3)
tmp1=head(b,c,lb)
tmp2=tail(b,c,lb)
ans1=min(len(head(a,tmp1,la)),len(tail(a,tmp1,la)))
if inner(a,tmp1,la,len(tmp1)):
  ans1=min(ans1,len(tmp1))
ans2=min(len(head(a,tmp2,la)),len(tail(a,tmp2,la)))
if inner(a,tmp2,la,len(tmp2)):
  ans2=min(ans2,len(tmp2))
ans3=10**18
if inner(b,c,lb,lc):
  ans3=min(len(head(a,c,la)),len(tail(a,c,la)))
  if inner(a,c,la,lc):
    ans3=min(ans3,lc)
ansbc=min(ans1,ans2,ans3)
tmp1=head(a,b,la)
lt1=len(tmp1)
tmp2=tail(a,b,la)
lt2=len(tmp2)
if lt1>=lc:
  ans1=min(len(head(c,tmp1,lc)),len(tail(c,tmp1,lc)))
  if inner(c,tmp1,lc,lt1):
    ans1=min(ans1,lt1)
else:
  ans1=min(len(head(tmp1,c,lt1)),len(tail(tmp1,c,lt1)))
  if inner(tmp1,c,lt1,c):
    ans1=min(ans1,c)
if lt2>=lc:
  ans2=min(len(head(c,tmp2,lc)),len(tail(c,tmp2,lc)))
  if inner(c,tmp2,lc,lt2):
    ans2=min(ans2,lt2)
else:
  ans2=min(len(head(tmp2,c,lt2)),len(tail(tmp2,c,lt2)))
  if inner(tmp2,c,lt2,lc):
    ans2=min(ans2,lc)
ans3=10**18
if inner(a,b,la,lb):
  ans3=min(len(head(b,c,lb)),len(tail(b,c,lb)))
  if inner(b,c,lb,lc):
    ans3=min(ans3,lc)
ansab=min(ans1,ans2,ans3)
ans=min(ansac,ansbc,ansab)
print(ans)

Submission status: Runtime Error

Solution code:
def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j] or S[i] == "?" or T[j] == "?":
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r
    return dp

al = input()

bl = input()

cl = input()
seq = [al,bl,cl]
ans = float("inf")
import itertools
for aal, bbl, ccl in list(itertools.permutations(seq, 3)):
    dp = solve(aal, bbl)
    for i in range(len(bbl)):
        k = 0
        if dp[i][0] == len(bbl) - i:
            k = len(bbl) - i
            break
    s = ""
    for a, b in zip(aal[len(aal)-k:], bbl[:k]):
        if a == "?":
            s += b
        else:
            s += a
    ddl = aal[:len(aal)-k]+ s + bbl[k:]
    print(aal,bbl,ccl, ddl)
    dp = solve(ddl, ccl)
    for i in range(len(ccl)):
        k = 0
        if dp[i][0] == len(ccl) - i:
            k = len(ccl) - i
            break
    print(len(ddl),len(ccl), k)
    ans = min(len(ddl) + len(ccl) - k, ans)
print(ans)

Submission status: Runtime Error

Solution code:
l = []
def calc3(s, N):
    if len(s) == N:
        print(s)
        l.append(s)
        return
    if len(s) > 0:
        c = s[-1]
        s2 = s[:]
        z = ord(c) - ord('a') + 2
        for i in range(z):
            st = s[:]
            st += chr(ord('a')+i)
            calc3(st[:], N)
    else:
        c = 'a'
        s += chr(ord(c))
        calc3(s[:], N)
def main():
    N = int(input())
    s = ''
    calc3(s[:], N)
main()

Submission status: Runtime Error

Solution code:
# input
H, W = map(int, input().split())

# process
if W == 1 or H == 1:
    print(1)

elif W%2 == 0:
    print((W//2) * H)
else:
    t = W//2
    if H%2 == 0:
        print((t*2 + 1) * (H//2))
    else:
        print((t*2 + 1) * (H//2) + t+1)

Submission status: Runtime Error

Solution code:
import sys
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
c = sys.stdin.readline().strip()
def match(x, y):
    for i in range(len(x)):
        if x[i] != "?":
            if y[i] != "?":
                if x[i] != y[i]:
                    return False
    return True

def do(a,b,c):
    #print (a,b,c)
    res = ""
    # a b c
    for p in range(len(a)):
        if match(a[p:], b[:len(b)-p]):
            # merge the string
            res = a[:p]
            for j in range(len(b)-p):
                if a[j+p] != "?":
                    res += a[j+p]
                else:
                    res += b[j]
            res += b[-p:]
            break
    if res == "":
        res = a+b
    #print(res)
    a = res[len(res)-len(b):]
    before = len(res)-len(b)
    b = c
    #print(before)
    res = ""
    for p in range(len(a)):
        if match(a[p:], b[:len(b)-p]):
            # merge the string
            return before + p
    
    return len(b) + before

tests = []
tests.append(do(a,b,c))
tests.append(do(a,c,b))
tests.append(do(b,a, c))
tests.append(do(b,c, a))
tests.append(do(c, b, a))
tests.append(do(c, a, b))
print(min(tests))

Submission status: Runtime Error

Solution code:
import itertools
import sys
input = sys.stdin.readline

def zalg(pattern, text):
  L = pattern + "$" + text
  N = len(L)
  Z = [0] * (N)
  i, j = 1, 0
  while i < N:
    while i + j < N and (L[j] == L[i + j] or L[j] == "?" or L[i + j] == "?"):
      j += 1
    Z[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N and k + Z[k] < j:
      Z[i + k] = Z[k]
      k += 1
    i += k
    j -= k
  return Z


a = input()
b = input()
c = input()

if a[-1] == "\n":
  a = a[:len(a) -1]
if b[-1] == "\n":
  b = b[:len(b) -1]
if c[-1] == "\n":
  c = c[:len(c) -1]

L = [a, b, c]

ans = len(a) + len(b) + len(c)

def nasu(x, y, z, ans):
  X = len(x)
  Y = len(y)
  Z = zalg(x, y)
  for i in range(X + 1, len(Z)):
    if Z[i] == X or Z[i] == len(Z) - i:
      ans = min(ans, honya(y, i - X - 1, x, z, ans))
  return ans

def honya(x, n, y, z, ans):
  x = x[:n] + y
  Z = zalg(z, X)
  L = len(z)
  X = len(x)
  for i in range(X + 1, len(Z)):
    if Z[i] == L:
      ans = min(ans, L)
    if Z[i] == len(Z) - i:
      ans = min(ans, len(Z) - i + len(x))
    
  return ans

for i in itertools.permutations([0, 1, 2]):
  x = L[i[0]]
  y = L[i[1]]
  z = L[i[2]]
  ans = min(ans, nasu(x, y, z, ans))

print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
p = len(a)
q = len(b)
r = len(c)


def func(a, b):
    p = len(a)
    q = len(b)
    for i in range(p):
        f = 0
        z = min(q, p - i)
        for j in range(z):
            if a[j + i] != "?" and b[j] != "?" and a[j + i] != b[j]:
                break
            f += 1
        if f == z:
            res = []
            for j in range(i):
                res.append(a[i])
            if z == q:
                for j in range(q):
                    if a[i + j] == "?" and b[j] == "?":
                        res.append("?")
                    else:
                        res.append(b[j])
                for j in range(p - (i + q), p):
                    res.append(a[j])
            else:
                for j in range(q):
                    if a[i + j] == "?" and b[j] == "?":
                        res.append("?")
                    else:
                        res.append(b[j])
            return res
    return p + q


res = []
res.append(func(func(a, b), c))
res.append(func(func(a, c), b))
res.append(func(func(b, a), c))
res.append(func(func(b, c), a))
res.append(func(func(c, a), b))
res.append(func(func(c, b), a))

res.sort(key=lambda x: len(x))
print(res[0])

Submission status: Runtime Error

Solution code:
import itertools
word = []
for _ in range(3):
    word.append(input())


def Z1(S):
    A = [0]*len(S)
    i = 1
    j = 0
    A[0] = len(S)
    while i < len(S):
        while i+j < len(S) and (S[j] == S[i+j] or S[i+j] == '?' or S[j] == '?'):
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while len(S)-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

def Z2(S):
    A = [0]*len(S)
    i = 1
    j = 0
    A[0] = len(S)
    while i < len(S):
        while i+j < len(S) and (S[j] == S[i+j] or S[i+j] == '?'):
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while len(S)-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A



ans = 10000

for w in itertools.permutations(word, 3):
    w = [w[0],w[1],w[2]]
    if w[1][0] != '?' and w[0][0] != '?' and w[1][0] != w[0][0]:
        f = Z2(w[0] + '0' + w[1])
    else:
        f = Z1(w[0] + '0' + w[1])

    dup = 0
    for i in range(len(w[1])):
        if f[len(w[0])+1+i] == len(w[1]) - i:
            dup += len(w[1]) - i
            break
    
    tmp = [x for x in w[1]]
    for k in range(i, len(w[1])):
        if tmp[k] == '?':
            tmp[k] = w[0][k-i]
    w[1] = ''.join(tmp)

    if w[2][0] != '?' and w[1][0] != '?' and w[2][0] != w[1][0]:
        s = Z2(w[1] + '0' + w[2])
    else:
        s = Z1(w[1] + '0' + w[2])
        
    for i in range(len(w[2])):
        if s[len(w[1])+1+i] == len(w[2]) - i:
            dup += len(w[2]) - i
            break

    ans = min(ans, len(w[2]) + len(w[1]) + len(w[0]) - dup)

print(ans)