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: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

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

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na+1):
        for r in range(nb+1):
            if (l==na or ab[l]==1) and (r==nb or bc[r]==1) and (l+r>=na or ac[l+r]==1):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

show_flg=False
z=a,b,c,ab,bc,ac;x=tri_check(*z);show(x,z)
ans=x
z=a,c,b,ac,cb,ab;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=b,a,c,ba,ac,bc;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=b,c,a,bc,ca,ba;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=c,a,b,ca,ab,cb;x=tri_check(*z);show(x,z)
ans=min(ans,x)
z=c,b,a,cb,ba,ca;x=tri_check(*z);show(x,z)
ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

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

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na+1):
        for r in range(nb+1):
            if (l==na or ab[l]==1) and (r==nb or bc[r]==1) and (l+r>=na or ac[l+r]==1):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

show_flg=False
x=tri_check(a,b,c,ab,bc,ac);show(x)
ans=x
x=tri_check(a,c,b,ac,cb,ac);show(x)
ans=min(ans,x)
x=tri_check(b,a,c,ba,ac,bc);show(x)
ans=min(ans,x)
x=tri_check(b,c,a,bc,ca,ba);show(x)
ans=min(ans,x)
x=tri_check(c,a,b,ca,ab,cb);show(x)
ans=min(ans,x)
x=tri_check(c,b,a,cb,ba,ca);show(x)
ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
#show_flg=True


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

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

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na):
        for r in range(nb):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

x=tri_check(a,b,c,ab,bc,ac);show(x)
ans=x
x=tri_check(a,c,b,ac,cb,ac);show(x)
ans=min(ans,x)
x=tri_check(b,a,c,ba,ac,bc);show(x)
ans=min(ans,x)
x=tri_check(b,c,a,bc,ca,ba);show(x)
ans=min(ans,x)
x=tri_check(c,a,b,ca,ab,cb);show(x)
ans=min(ans,x)
x=tri_check(c,b,a,cb,ba,ca);show(x)
ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

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

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na):
        for r in range(nb):
            if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

x=tri_check(a,b,c,ab,bc,ac);show(x)
ans=x
x=tri_check(a,c,b,ac,cb,ac);show(x)
ans=min(ans,x)
x=tri_check(b,a,c,ba,ac,bc);show(x)
ans=min(ans,x)
x=tri_check(b,c,a,bc,ca,ba);show(x)
ans=min(ans,x)
x=tri_check(c,a,b,ca,ab,cb);show(x)
ans=min(ans,x)
x=tri_check(c,b,a,cb,ba,ca);show(x)
ans=min(ans,x)

print(ans)

Submission status: Wrong Answer

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 i in range(1,len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  ab = len(a)+len(b)
  abc = float("inf")
  for d in merge(a,b):
    if len(d) > abc:
      break
    l = len(next(merge(d, c)))
    abc = min(abc, l)
  if abc <= ab:
    return abc
  
  return abc

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

print(min_merge(a,b,c))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))

def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(na-i):
            if j<nb and (a[i+j]==b[j] or a[i+j]=='?' or b[j]=='?'):
                pass
            else:
                fl=False
                break
        if fl:
            rt[i]=1
    return rt

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

def tri_check(a,b,c,ab,bc,ac):
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    for l in range(na):
        for r in range(nb):
            if ab[l]==1 and bc[r]==1 and (l+nb>=na or ac[l+r]==1):
                rt=min(rt,na+nb+nc-(na-l)-(nb-r))
    return rt

ans=tri_check(a,b,c,ab,bc,ac)
ans=min(ans,tri_check(a,c,b,ac,cb,ac))
ans=min(ans,tri_check(b,a,c,ba,ac,bc))
ans=min(ans,tri_check(b,c,a,bc,ca,ba))
ans=min(ans,tri_check(c,a,b,ca,ab,cb))
ans=min(ans,tri_check(c,b,a,cb,ba,ca))
print(ans)

Submission status: Wrong Answer

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


def check(x, y):
    r = ""
    for i, j in zip(x, y):
        if i == j:
            r += i
            continue
        if i == "?" and j == "?":
            r += "?"
            continue
        if j == "?":
            r += i
            continue
        if i == "?":
            r += j
        return ""
    return r


# x, yの順で結合する
def unite(x, y):
    cnt = min(len(x), len(y))
    while True:
        r = x[-cnt:]
        s = y[:cnt]
        if check(r, s):
            return x[:-cnt] + check(r, s) + y[cnt:]
        else:
            cnt -= 1
        if cnt == 0:
            break
    return x + y


ans = len(unite(unite(a, b), c))
ans = min(ans, len(unite(unite(a, c), b)))
ans = min(ans, len(unite(unite(b, a), c)))
ans = min(ans, len(unite(unite(b, c), a)))
ans = min(ans, len(unite(unite(c, a), b)))
ans = min(ans, len(unite(unite(c, b), a)))
ans = min(ans, len(unite(a, unite(b, c))))
ans = min(ans, len(unite(a, unite(c, b))))
ans = min(ans, len(unite(b, unite(a, c))))
ans = min(ans, len(unite(b, unite(c, a))))
ans = min(ans, len(unite(c, unite(a, b))))
ans = min(ans, len(unite(c, unite(b, a))))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

A,B,C = read().decode().split()

A = np.array(list(A))
B = np.array(list(B))
C = np.array(list(C))

M = 2020

def can_match(x,y):
    L = min(len(x), len(y))
    x = x[:L]
    y = y[:L]
    return np.all((x == '?') | (y == '?') | (x == y))

def solve(A,B,C,LA,LB,LC):
    BA = [True] * (M)
    for i in range(M):
        BA[i] = can_match(A[i:], B)
    CA = [True] * (M+M)
    for i in range(M+M):
        CA[i] = can_match(A[i:], C)
    CB = [True] * (M)
    for i in range(M):
        CB[i] = can_match(B[i:], C)

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    solve(A,B,C,LA,LB,LC)
print(answer)

Submission status: Wrong Answer

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=0):
  for i in range(abs(lr),len(b)):
    if lr>=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], i
    if lr<=0:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], -i
  yield a+b, len(b)
  yield b+a, -len(b)

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
  if lr > 0:
    lr = len(b)+1-lr
  else:
    lr = -len(b)-1-lr
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)

Submission status: Wrong Answer

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=0):
  for i in range(abs(lr),len(b)):
    if lr>=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], i
    if lr<=0:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], -i
  yield a+b, len(b)
  yield b+a, -len(b)

a="a?c"
b="der"
c="cod"
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
  if lr > 0:
    lr = len(b)+1-lr
  else:
    lr = -len(b)-1-lr
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)

Submission status: Wrong Answer

Solution code:
def match(x, y):
    return x == y or x == '?' or y == '?'


def check(s, t):
    ANS = [1] * (10 ** 5)
    S = len(s); T = len(t)
    for i in range(S):
        for j in range(T):
            if not match(s[i], t[j]):
                ANS[i - j + 50000] = 0
    return ANS


a = input()
b = input()
c = input()
lenA = len(a)
lenB = len(b)
lenC = len(c)

AB = check(a, b)
AC = check(a, c)
BC = check(b, c)

ans = lenA + lenB + lenC
for i in range(-lenB, lenA + lenB + 1):
    for j in range(-lenC, lenA + lenC + 1):
        if AB[i + 50000] and AC[j + 50000] and BC[j - i + 50000]:
            L = min(0, min(i, j))
            R = max(lenA, max(lenB + i, lenC + j))
            ans = min(ans, R - L)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return input().rstrip()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("inf")

#solve
def solve():
    a = S()
    b = S()
    c = S()
    def f(a, b, c):
        lena, lenb, lenc = len(a), len(b), len(c)
        dpab = [inf] * (lena + 1)
        dpbc = [inf] * (lenb + 1)
        dpac = [inf] * (lena + 1)
        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenb):
                if l == lena:
                    break
                if a[l] == b[r] or a[l] == "?" or b[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpab[tl] = max(tl + lenb, lena)

        for l in range(lenb + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lenb:
                    break
                if b[l] == c[r] or b[l] == "?" or c[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpbc[tl] = max(tl + lenc, lenb)

        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lena:
                    break
                if a[l] == c[r] or a[l] == "?" or c[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpac[tl] = max(tl + lenc, lena)

        res = lena + lenb + lenc
        for l in range(lena + 1):
            for r in range(lenb + 1):
                lr = l + r
                if dpab[l] != inf and dpbc[r] != inf:
                    if lr > lena:
                        res = min(l + dpbc[r], res)
                    else:
                        if dpac[lr] != inf:
                            if dpbc[r] == lenb:
                                res = min(res, dpab[l])
                            else:
                                res = min(res, dpac[lr])
            for r in range(r + 1, lena + 1):
                if dpab[l] == lena:
                    if dpac[r] != inf:
                        res = min(res, dpac[r])
        # print(res)
        return res

    ans = len(a) + len(b) + len(c)
    ans = min(ans, f(a, b, c))
    ans = min(ans, f(a, c, b))
    ans = min(ans, f(b, a, c))
    ans = min(ans, f(b, c, a))
    ans = min(ans, f(c, b, a))
    ans = min(ans, f(c, a, b))
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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(merge2(d, b, lr)))
  abc = min(abc, l)
print(abc)

Submission status: Wrong Answer

Solution code:

def same(x: str, y: str):
    for a, b in zip(x, y):
        if a == '?' or b == '?':
            continue
        if a != b:
            return False
    return True


def main():
    a = input()
    b = input()
    c = input()
    length = len(a)
    # AB
    overlap_ab = 0
    for i in range(length):
        if same(a[i:], b[:length-i]):
            overlap_ab = length - i
            break
    # BC
    overlap_bc = 0
    for i in range(length):
        if same(b[i:], c[:length-i]):
            overlap_bc = length - i
            break
    # CA
    overlap_ca = 0
    for i in range(length):
        if same(c[i:], a[:length-i]):
            overlap_ca = length - i
            break
    # BA
    overlap_ba = 0
    for i in range(length):
        if same(b[i:], a[:length-i]):
            overlap_ba = length - i
            break
    # CB
    overlap_cb = 0
    for i in range(length):
        if same(c[i:], b[:length-i]):
            overlap_cb = length - i
            break
    # AC
    overlap_ac = 0
    for i in range(length):
        if same(a[i:], c[:length-i]):
            overlap_ac = length - i
            break

    top = max([overlap_ab + overlap_bc,
               overlap_bc + overlap_ca,
               overlap_ca + overlap_ab,
               overlap_ba + overlap_ac,
               overlap_ac + overlap_cb,
               overlap_cb + overlap_ba])
    print(length * 3 - top)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
maxn = 2000 * 3 + 10
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 - d] != '?' 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 (0 <= i + j - maxnh < maxn) and 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: Wrong Answer

Solution code:

def same(x: str, y: str):
    for a, b in zip(x, y):
        if a == '?' or b == '?':
            continue
        if a != b:
            return False
    return True


def main():
    a = input()
    b = input()
    c = input()
    length = len(a)
    # AB
    overlap_ab = 0
    for i in range(length):
        if same(a[i:], b[:length-i]):
            overlap_ab = length - i
            break
    # BC
    overlap_bc = 0
    for i in range(length):
        if same(b[i:], c[:length-i]):
            overlap_bc = length - i
            break
    # CA
    overlap_ca = 0
    for i in range(length):
        if same(c[i:], a[:length-i]):
            overlap_ca = length - i
            break
    # BA
    overlap_ba = 0
    for i in range(length):
        if same(b[i:], a[:length-i]):
            overlap_ba = length - i
            break
    # CB
    overlap_cb = 0
    for i in range(length):
        if same(c[i:], b[:length-i]):
            overlap_cb = length - i
            break
    # AC
    overlap_ac = 0
    for i in range(length):
        if same(a[i:], c[:length-i]):
            overlap_ac = length - i
            break

    top1, top2 = list(sorted([overlap_ab, overlap_bc, overlap_ca, overlap_ba, overlap_cb, overlap_ac]))[-2:]
    print(length * 3 - top1 - top2)


if __name__ == '__main__':
    main()