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:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def concat(x,y):
    len_x = len(x)
    len_y = len(y)
    for i in range(len_x+1):
        z = x[:i]
        ng = False
        for j in range(len_y):
            # log(x,y,i,j)
            if i+j >= len_x:
                z += y[j]
            elif x[i+j]=="?" or y[j]=="?" or x[i+j]==y[j]:
                if x[i+j]=="?" and y[j]=="?":
                    z += "?"
                else:
                    z += x[i+j] if x[i+j] != "?" else y[j]
            else:
                ng = True
                break
        if not ng:
            log(x,y,z+x[i+j:])
            return z+x[i+j:]
    log("XXX")

def solve(x,y,z):
    return min(len(concat(concat(x,y), z)), len(concat(x, concat(y,z))))

print(min(
    solve(a,b,c),
    solve(a,c,b),
    solve(b,a,c),
    solve(b,c,a),
    solve(c,a,b),
    solve(c,b,a)
))

Submission status: Wrong Answer

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

def make_table(w):
	n = len(w)
	t = [-1, 0] + [None] * (n - 2)
	i = 2
	j = 0
	
	while i < n:
		c1 = w[i - 1]
		c2 = w[j]
		if c1 == c2 or c1 == "?" or c2 == "?":
			t[i] = j + 1
			i += 1
			j += 1
		elif j > 0:
			j = t[j]
		else:
			t[i] = 0
			i += 1
	return t

def search(s, w, t):
	n1 = len(s)
	n2 = len(w)
	m = 0
	i = 0
	while m < n1:
		c1 = s[m + i]
		c2 = w[i]
		if c1 == c2 or c1 == "?" or c2 == "?":
			i += 1
		else:
			m += i - t[i]
			if i > 0:
				i = t[i]
		if i >= n2 or m + i >= n1:
			return m
	return n1

import itertools

def merge(a, b):
	n = search(a, b, make_table(b))
	c = list(a) + ["?"] * (len(b) + n - len(a))
#	print(a, b, n, c)
	for i in range(len(b)):
		j = n + i
#		print(i, j, c[j], b[i])
		if c[j] == "?":
			c[j] = b[i]
	return "".join(c)

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

for a, b, c in itertools.permutations([a, b, c]):
	tmp1 = merge(a, b)
	tmp2 = merge(tmp1, c)
#	print(a, b, c, tmp1, tmp2)
	if len(tmp2) < min_length:
		min_length = len(tmp2)

print(min_length)

Submission status: Wrong Answer

Solution code:
a = list(input())
b = list(input())
c = list(input())
n0 = len(a)
n1 = len(b)
n2 = len(c)
al = []
def mae(a,b):
    n0 = len(a)
    n1 = len(b)
    al = []
    now = []
    count = 0
    for i in range(n1):
        if a[0] == b[i] or a[0] == "?" or b[i] == "?":
            now2 = now
            count2 = 0
            for j in range(min(n1-i,n0)):
                if a[j] != b[j+i] and a[j] != "?" and b[j+i] != "?":
                    break
                else:
                    count2 += 1
                    now2.append(a[j])
            count = max(count,count2)
            al.append([now2,count2])
        now.append(b[i])
    return al,count
def ushiro(a,b):
    n0 = len(a)
    n1 = len(b)
    al = []
    now = []
    count = 0
    for i in range(n1-1,-1,-1):
        if a[n0-1] == b[i] or a[n0-1] == "?" or b[i] == "?":
            now2 = now
            count2 = 0
            for j in range(min(i,n0)):
                if a[n0-1-j] != b[i-j] and a[n0-1-j] != "?" and b[i-j] != "?":
                    break
                else:
                    count2 += 1
                    now2.append(a[j])
            count = max(count,count2)
            al.append([now2,count2])
        now.append(b[i])
    return al,count
ansl = [0]
c1,k = mae(a,b)
c2,p = ushiro(a,b)
for i in c1:
    c3,k1 = mae(c,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(c,i[0])
    ansl.append(k1+i[1])
c1,k = mae(b,a)
c2,p = ushiro(b,a)
for i in c1:
    c3,k1 = mae(c,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(c,i[0])
    ansl.append(k1+i[1])
c1,k = mae(a,c)
c2,p = ushiro(a,c)
for i in c1:
    c3,k1 = mae(b,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(b,i[0])
    ansl.append(k1+i[1])
c1,k = mae(c,a)
c2,p = ushiro(c,a)
for i in c1:
    c3,k1 = mae(b,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(b,i[0])
    ansl.append(k1+i[1])
c1,k = mae(c,b)
c2,p = ushiro(c,b)
for i in c1:
    c3,k1 = mae(a,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(a,i[0])
    ansl.append(k1+i[1])
c1,k = mae(b,c)
c2,p = ushiro(b,c)
for i in c1:
    c3,k1 = mae(a,i[0])
    ansl.append(k1+i[1])
for i in c2:
    c3,k1 = ushiro(a,i[0])
    ansl.append(k1+i[1])
print(n0+n1+n2-max(ansl))

Submission status: Wrong Answer

Solution code:
def M(s,t):
    ls = len(s)
    lt = len(t)
    for k in range(ls):
        i = k
        j = 0
        ans = s[:i]
        while i < ls and j < lt:
            if s[i] == '?' and t[j] == '?':
                ans += '?'
            elif s[i] == '?':
                ans += t[j]
            elif t[j] == '?':
                ans += s[i]
            elif s[i] == t[j]:
                ans += s[i]
            else:
                break
            i += 1
            j += 1

        if  j == lt :
            return ans + s[i:]
        if  i == ls:
            return ans + t[j:]
    return s + t   
        
def main():
    a = input()
    b = input()
    c = input()

    tmp1 = len( M(M(a,b),c) )
    tmp2 = len( M(M(a,c),b) )
    tmp3 = len( M(M(b,a),c) )
    tmp4 = len( M(M(b,c),a) )
    tmp5 = len( M(M(c,a),b) )
    tmp6 = len( M(M(c,b),a) )
    ans = min(tmp1,tmp2,tmp3,tmp4,tmp5,tmp6)
    print(ans)
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import permutations
def main():
    C = [ input() for _ in range(3)]
    LC = [ len(c) for c in C]
    ans = sum(LC)
    for P in permutations( range(3)):
        now = sum(LC)
        a, b, c = P[0], P[1], P[2]
        X, Y, Z = C[a], C[b], C[c]
        x, y, z = LC[a], LC[b], LC[c]
        for i in range(x):
            # if x - i > y:
            #     continue
            check = True
            for j in range(i, min(x,i+y)):
                if X[j] == '?' or Y[j-i] == '?' or X[j] == Y[j-i]:
                    continue
                check = False
                break
            if check:
                if i+y <= x:
                    W = X[:i]
                    for j in range(i,i+y):
                        if X[j] == '?' or Y[j-i] == '?':
                            W += '?'
                        else:
                            W += X[j]
                    W += X[i+y:]
                    now -= y
                    y = x
                else:
                    W = X[:i]
                    for j in range(i,x):
                        if X[j] == '?' or Y[j-i] == '?':
                            W += '?'
                        else:
                            W += X[j]
                    W += Y[x-i:]
                    now -= x-i
                    y = now-z
                break
        else:
            W = X+Y
            y += x
        for i in range(y):
            check = True
            for j in range(i, min(y,i+z)):
                if W[j] == '?' or Z[j-i] == '?' or W[j] == Z[j-i]:
                    continue
                check = False
                break
            if check:
                if i+z <= y:
                    now -= z
                else:
                    now -= y-i
                break
        print(X, Y, W, Z, y, now)
        if now < ans:
            ans = now
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
s = a
for i in range(len(s)):
    for j in range(min(len(s) - i, len(b))):
        if s[i + j] != b[j] and s[i + j] != '?' and b[j] != '?':
            break
    else:
        t1 = i
        break
else:
    t1 = len(s)
for i in range(len(b)):
    for j in range(min(len(b) - i, len(s))):
        if b[i + j] != s[j] and b[i + j] != '?' and s[j] != '?':
            break
    else:
        t2 = i
        break
else:
    t2 = len(b)
if max(len(s), len(b) + t1) < max(len(b), len(s) + t2):
    idx = len(s) - t1
    if idx < len(b):
        s += b[idx:]
else:
    idx = len(b) - t2
    if idx < len(s):
        s = b + s[idx:]
for i in range(len(s)):
    for j in range(min(len(s) - i, len(c))):
        if s[i + j] != c[j] and s[i + j] != '?' and c[j] != '?':
            break
    else:
        t1 = i
        break
else:
    t1 = len(s)
for i in range(len(c)):
    for j in range(min(len(c) - i, len(s))):
        if c[i + j] != s[j] and c[i + j] != '?' and s[j] != '?':
            break
    else:
        t2 = i
        break
else:
    t2 = len(c)
if max(len(s), len(c) + t1) < max(len(c), len(s) + t2):
    idx = len(s) - t1
    if idx < len(c):
        s += c[idx:]
else:
    idx = len(c) - t2
    if idx < len(s):
        s = c + s[idx:]
ans1 = len(s)

a, b, c = a, c, b
s = a
for i in range(len(s)):
    for j in range(min(len(s) - i, len(b))):
        if s[i + j] != b[j] and s[i + j] != '?' and b[j] != '?':
            break
    else:
        t1 = i
        break
else:
    t1 = len(s)
for i in range(len(b)):
    for j in range(min(len(b) - i, len(s))):
        if b[i + j] != s[j] and b[i + j] != '?' and s[j] != '?':
            break
    else:
        t2 = i
        break
else:
    t2 = len(b)
if max(len(s), len(b) + t1) < max(len(b), len(s) + t2):
    idx = len(s) - t1
    if idx < len(b):
        s += b[idx:]
else:
    idx = len(b) - t2
    if idx < len(s):
        s = b + s[idx:]
for i in range(len(s)):
    for j in range(min(len(s) - i, len(c))):
        if s[i + j] != c[j] and s[i + j] != '?' and c[j] != '?':
            break
    else:
        t1 = i
        break
else:
    t1 = len(s)
for i in range(len(c)):
    for j in range(min(len(c) - i, len(s))):
        if c[i + j] != s[j] and c[i + j] != '?' and s[j] != '?':
            break
    else:
        t2 = i
        break
else:
    t2 = len(c)
if max(len(s), len(c) + t1) < max(len(c), len(s) + t2):
    idx = len(s) - t1
    if idx < len(c):
        s += c[idx:]
else:
    idx = len(c) - t2
    if idx < len(s):
        s = c + s[idx:]
ans2 = len(s)
print(min(ans1, ans2))

Submission status: Wrong Answer

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

def shiritori(p,q):
	len_p = len(p)
	len_q = len(q)

	cond = 0
	for i in range(len_p+1):
		j = 0
		while True:
			if i == len_p or j == len_q:
				cond = 1
				break
			if p[i] == '?' or q[j] == '?':
				i += 1
				j += 1

			else:
				if p[i] == q[j]:
					i += 1
					j += 1
				else:
					break

		if cond:
			if j == 0:
				return p + q
			else:
				return p[:-j] + q

		else:
			continue

ans = 10**9
ans = min(ans, len(shiritori(shiritori(a,b),c)))
ans = min(ans, len(shiritori(shiritori(a,c),b)))
ans = min(ans, len(shiritori(shiritori(b,a),c)))
ans = min(ans, len(shiritori(shiritori(b,c),a)))
ans = min(ans, len(shiritori(shiritori(c,a),b)))
ans = min(ans, len(shiritori(shiritori(c,b),a)))

print(ans)

Submission status: Wrong Answer

Solution code:
a=input()
b=input()
c=input()
l=len(a)+len(b)+len(c)

def hatena_equal(p,q):
    for i in range(len(p)):
        if p[i]==q[i] or p[i]=='?' or q[i]=='?':
            return True
        else:
            return False

def gattai(x,y):
    mm=min(len(x),len(y))
    score=0
    for i in range(mm):
        xx=x[i:]
        yy=y[:mm-i]
        if hatena_equal(xx,yy):
            score=len(xx)
            break
    return score

ABC=l-gattai(a,b)-gattai(b,c)
ACB=l-gattai(a,c)-gattai(c,b)
BAC=l-gattai(b,a)-gattai(a,c)
BCA=l-gattai(b,c)-gattai(c,a)
CAB=l-gattai(c,a)-gattai(a,b)
CBA=l-gattai(c,b)-gattai(b,a)

print(min([ABC,ACB,BAC,BCA,CAB,CBA]))

Submission status: Wrong Answer

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


def Z(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):
    f = Z(w[0] + '0' + w[1])
    s = Z(w[1] + '0' + w[2])

    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

    for i in range(len(w[2])):
        if s[len(w[1])+1+i] == len(w[2]) - i:
            dup += len(w[2]) - i

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

print(ans)

Submission status: Wrong Answer

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

def check_two(x, y):
    for i in range(len(x)):
        ok = True
        now = []
        for j in range(len(x[i:])):
            if i + j >= len(x) or j >= len(y):
                now = []
                break
            if x[i + j] != y[j] and x[i + j] != "?" and y[j] != "?":
                ok = False
                now = []
                break
            else:
                if x[i + j] == "?":
                    now.append(y[j])
                else:
                    now.append(x[i + j])
        if ok == True:
            break
    if now == []:
        return x + y
    else:
        return x[:i] + "".join(now) + y[j + 1:]

s1 = check_two(check_two(a, b),c)
s2 = check_two(check_two(a, c),b)
s3 = check_two(check_two(b, a),c)
s4 = check_two(check_two(b, c),a)
s5 = check_two(check_two(c, b),a)
s6 = check_two(check_two(c, a),b)

print(min(len(s1),len(s2),len(s3),len(s4),len(s5),len(s6)))

Submission status: Wrong Answer

Solution code:
a=list(input())
b=list(input())
c=list(input())
AB=0;AC=0;BC=0;BA=0;CA=0;CB=0
for i in range(1,min(len(a),len(b))+1):
  A=a[len(a)-i:len(a)]
  B=b[0:i]
  ct=0
  for j in range(len(A)):
    if A[j]==B[j] or A[j]=='?' or B[j]=='?':
      ct+=1
    if ct==len(A):
      AB=ct

for i in range(1,min(len(a),len(c))+1):
  A=a[len(a)-i:len(a)]
  C=c[0:i]
  ct=0
  for j in range(len(A)):
    if A[j]==C[j] or A[j]=='?' or C[j]=='?':
      ct+=1
    if ct==len(A):
      AC=ct

for i in range(1,min(len(b),len(c))+1):
  B=b[len(b)-i:len(b)]
  C=c[0:i]
  ct=0
  for j in range(len(B)):
    if B[j]==C[j] or B[j]=='?' or C[j]=='?':
      ct+=1
    if ct==len(B):
      BC=ct

for i in range(1,min(len(b),len(a))+1):
  B=b[len(b)-i:len(b)]
  A=a[0:i]
  ct=0
  for j in range(len(B)):
    if B[j]==A[j] or B[j]=='?' or A[j]=='?':
      ct+=1
    if ct==len(B):
      BA=ct

for i in range(1,min(len(c),len(a))+1):
  C=c[len(c)-i:len(c)]
  A=a[0:i]
  ct=0
  for j in range(len(C)):
    if C[j]==A[j] or C[j]=='?' or A[j]=='?':
      ct+=1
    if ct==len(C):
      CA=ct

for i in range(1,min(len(c),len(b))+1):
  C=c[len(c)-i:len(c)]
  B=b[0:i]
  ct=0
  for j in range(len(C)):
    if C[j]==B[j] or C[j]=='?' or B[j]=='?':
      ct+=1
    if ct==len(C):
      CB=ct

n=len(a)+len(b)+len(c)
ans=[n-AB-BC,n-AC-CB,n-BA-AC,n-BC-CA,n-CA-AB,n-CB-BA]
print(min(ans))

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
def input():
	return sys.stdin.readline()[:-1]

def same(A, B):
	L = len(A)
	for l in range(L):
		if A[l] == B[l] or A[l] == "?" or B[l] == "?":
			pass
		else:
			return False
	return True

t = [input() for _ in range(3)]

a, b, c = t
la, lb, lc = len(a), len(b), len(c)

cross = [[0 for _ in range(3)] for _ in range(3)]

for i in range(1, min(len(a), len(b))+1):
	if same(a[la-i:], b[:i]):
		cross[0][1] = i
	if same(b[lb-i:], a[:i]):
		cross[1][0] = i

for i in range(1, min(len(b), len(c))+1):
	if same(b[lb-i:], c[:i]):
		cross[1][2] = i
	if same(c[lc-i:], b[:i]):
		cross[2][1] = i

for i in range(1, min(len(c), len(a))+1):
	if same(c[lc-i:], a[:i]):
		cross[2][0] = i
	if same(a[la-i:], c[:i]):
		cross[0][2] = i

def In(x, y):
	if len(x) > len(y):
		return False
	else:
		for i in range(len(y)-len(x)+1):
			if same(x, y[i:i+len(x)]):
				return True
	return False

if In(a, b):
	cross[0][1] = la
	cross[1][0] = la

if In(b, a):
	cross[0][2] = la
	cross[2][0] = la

if In(b, a):
	cross[0][1] = lb
	cross[1][0] = lb

if In(b, c):
	cross[2][1] = lb
	cross[1][2] = lb

if In(c, a):
	cross[0][2] = lc
	cross[2][0] = lc

if In(c, b):
	cross[2][1] = lc
	cross[1][2] = lc

ans = la+lb+lc
for p in permutations(range(3)):
	ans = min(ans, la+lb+lc - cross[p[0]][p[1]] - cross[p[1]][p[2]])
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

def concat(x,y):
    len_x = len(x)
    len_y = len(y)
    for i in range(len_x+1):
        z = x[:i]
        ng = False
        for j in range(len_y):
            # log(x,y,i,j)
            if i+j >= len_x:
                z += y[j]
            elif x[i+j]=="?" or y[j]=="?" or x[i]==y[j]:
                if x[i+j]=="?" and y[j]=="?":
                    z += "?"
                else:
                    z += x[i+j] if x[i+j] != "?" else y[j]
            else:
                ng = True
                break
        if not ng:
            # log(x,y,z)
            return z
    log("XXX")

def solve(x,y,z):
    return len(concat(concat(x,y), z))

print(min(
    solve(a,b,c),
    solve(a,c,b),
    solve(b,a,c),
    solve(b,c,a),
    solve(c,a,b),
    solve(c,b,a)
))

Submission status: Wrong Answer

Solution code:
import itertools

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

def eq(s,t,i):

    for _s,_t in zip(s[-1*i:],t[:i]):

        if _s==_t:
            pass
        elif _s=='?' or _t=='?':
            pass
        else:
            return False
    return True

def join(s,t):
    retval=0
    for i in range(min(len(s),len(t))+1):
        if eq(s,t,i):
            retval=i

    prob1=s[:len(s)-retval]+t
    prob2=s+t[retval:]
    if prob1.count('?')<prob2.count('?'):
        return prob1
    else:
        return prob2

retval=10**10
for strs in itertools.permutations([a,b,c]):
    p=strs[0]
    q=strs[1]
    r=strs[2]
    pqr=join(join(p,q),r)
    pqr2=join(p,join(q,r))
    if(len(pqr)<retval):
        retval=len(pqr)
    if(len(pqr2)<retval):
        retval=len(pqr2)
print(retval)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from itertools import permutations
    input = sys.stdin.readline

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    S = [A, B, C]

    ans = 10**5
    for abc in permutations(list(range(3))):
        a, b, c = S[abc[0]], S[abc[1]], S[abc[2]]
        na = len(a)
        nb = len(b)
        nc = len(c)

        flg = 0
        for i in range(na):
            s = [k for k in a[:i]]
            ok = 1
            for j in range(na-i):
                if j >= nb:
                    pass
                else:
                    #print(i+j, j)
                    if a[i+j] == b[j]:
                        s.append(b[j])
                    else:
                        if a[i+j] == '?':
                            s.append(b[j])
                        elif b[j] == '?':
                            s.append(a[i+j])
                        else:
                            ok = 0
            #print(s)
            if ok:
                flg = 1
                for k in range(na-i, nb):
                    s.append(b[k])
                break
        if not flg:
            s = [k for k in a+b]
        ns = len(s)

        flg = 0
        for i in range(ns):
            t = [k for k in s[:i]]
            ok = 1
            for j in range(ns-i):
                if j >= nc:
                    pass
                else:
                    if s[i+j] == c[j]:
                        t.append(c[j])
                    else:
                        if s[i+j] == '?':
                            t.append(c[j])
                        elif c[j] == '?':
                            t.append(s[i+j])
                        else:
                            ok = 0
            if ok:
                for k in range(ns-i, nc):
                    t.append(c[k])
                flg = 1
                break
        if not flg:
            ans = min(ans, ns + nc)
        else:
            ans = min(ans, len(t))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and (s[j] == s[i+j] or s[i+j] == "?"):
                    j += 1
                z[i] = j
                c = i
        return z

    s = [input() for i in range(3)]
    ans = float("inf")
    for p in permutations(range(3)):
        a,b,c = s[p[0]],s[p[1]],s[p[2]]
        z = Z_algorithm(b+a)[len(b):]
        d = a+b
        zc = Z_algorithm(c+d)[len(c):]
        res = len(d)+len(c)
        for i in range(len(d)):
            if zc[i] >= len(d)-i or zc[i] >= len(c):
                k = max(len(d),i+len(c))
                if k < res:
                    res = k

        for j in range(len(a)):
            if z[j] >= len(a)-j or z[j] >= len(b):
                d = a[:j]
                for i in range(max(len(a)-j,len(b))):
                    k = i+j
                    if k < len(a):
                        if i < len(b) and a[k] == "?":
                            d += b[i]
                        else:
                            d += a[k]
                    else:
                        d += b[i]
            else:
                continue
            zc = Z_algorithm(c+d)[len(c):]
            k = len(d)+len(c)
            for i in range(len(d)):
                if zc[i] >= len(d)-i or zc[i] >= len(c):
                    m = max(len(d),i+len(c))
                    if m < k:
                        k = m
            if k < res:
                res = k
        if res < ans:
            ans = res
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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


for i in range(len(a)):
    flag = True
    tmp = i
    for j in range(len(c)):
        if tmp >= len(a):
            break
        if a[tmp] == c[j]:
            tmp += 1
        elif a[tmp] == '?' or c[j] == '?':
            tmp += 1
        elif a[tmp] != c[j]:
            flag = False
            break

    if flag:
        for x in range(len(c)):
            if i+x >= len(a):
                a += c[x]
            a[i+x] = c[x]
        break

print(a)


for i in range(len(a)):
    flag = True
    tmp = i
    for j in range(len(b)):
        if tmp >= len(a):
            break
        if a[tmp] == b[j]:
            tmp += 1
        elif a[tmp] == '?' or b[j] == '?':
            tmp += 1
        elif a[tmp] != b[j]:
            flag = False
            break

    if flag:
        for x in range(len(b)):
            if i+x >= len(a):
                a += b[x]
            a[i+x] = b[x]
        break

for i in range(len(a)):
    flag = True
    tmp = i
    for j in range(len(c)):
        if tmp >= len(a):
            break
        if a[tmp] == c[j]:
            tmp += 1
        elif a[tmp] == '?' or c[j] == '?':
            tmp += 1
        elif a[tmp] != c[j]:
            flag = False
            break

    if flag:
        for x in range(len(c)):
            if i+x >= len(a):
                a += c[x]
            a[i+x] = c[x]
        break

print(len(a))

Submission status: Wrong Answer

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

def make_table(w):
	n = len(w)
	t = [-1, 0] + [None] * (n - 2)
	i = 2
	j = 0
	
	while i < n:
		c1 = w[i - 1]
		c2 = w[j]
		if c1 == c2 or c1 == "?" or c2 == "?":
			t[i] = j + 1
			i += 1
			j += 1
		elif j > 0:
			j = t[j]
		else:
			t[i] = 0
			i += 1
	return t

def search(s, w, t):
	n1 = len(s)
	n2 = len(w)
	m = 0
	i = 0
	while m < n1:
		c1 = s[m + i]
		c2 = w[i]
		if c1 == c2 or c1 == "?" or c2 == "?":
			i += 1
		else:
			m += i - t[i]
			if i > 0:
				i = t[i]
		if i >= n2 or m + i >= n1:
			return m
	return n1

import itertools

def merge(a, b):
	n = search(a, b, make_table(b))
	c = list(a) + ["?"] * (len(b) + n - len(a))
	for i in range(len(b) + n - len(a)):
		j = n + i
		if c[j] == "?":
			c[j] = b[i]
	return "".join(c)

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

for a, b, c in itertools.permutations([a, b, c]):
	tmp = merge(merge(a, b), c)
	if len(tmp) < min_length:
		min_length = len(tmp)

print(min_length)

Submission status: Wrong Answer

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

def match(a, b, start):
    l = float('inf')
    tmpi = 0
    for i in range(start, len(a)):
        aa = a[i:]
        if len(aa) < len(b):
            bb = b[:len(aa)]
        else:
            aa = aa[:len(b)]
            bb = b

        f = True
        for j in range(len(aa)):
            if aa[j] != bb[j] and aa[j] != '?' and bb[j] != '?':
                f = False
                break
            elif aa[j] == '?' and bb[j] != '?':
                aa[j] == bb[j]
            elif aa[j] != '?' and bb[j] == '?':
                bb[j] == aa[j]
        if f:
            if max(i + len(b), len(a)) < l:
                l = i + len(b)
                tmpi = i

    if l == float('inf'):
        return a + b
    else:
        if len(a[tmpi:]) < len(b):
            return a[:tmpi] + b
        else:
            return a

l = float('inf')
for seq in [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]:
    s1 = match(seq[0], seq[1], 0)
    s2 = match(s1, seq[2], 0)
    l = min(l, len(s2))

    s1 = match(seq[0][::-1], seq[1][::-1], 0)
    s2 = match(s1, seq[2][::-1], 0)
    l = min(l, len(s2))

print(l)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
if "?" in a:
    for i in range(len(a)):
        if a[0] == "?":
            a = a[1:]
        else:
            break
    for j in range(len(a)):
        if a[-1] == "?":
            a = a[:-1]
        else:
            break
if "?" in b:
    for i in range(len(b)):
        if b[0] == "?":
            b = b[1:]
        else:
            break
    for j in range(len(b)):
        if b[-1] == "?":
            b = b[:-1]
        else:
            break
if "?" in c:
    for i in range(len(c)):
        if c[0] == "?":
            c = c[1:]
        else:
            break
    for j in range(len(c)):
        if c[-1] == "?":
            c = c[:-1]
        else:
            break
s = (a+b+c)
s = set(s)
#print(s)
print(len(s))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def same(a,b,l):
        res=a[:l]
        w=0
        for c0,c1 in zip(a[l:],b):
            if c0!="?" and c1!="?" and c0!=c1:
                return "NO"
            w+=1
            if c0!="?":res+=c0
            elif c1!="?":res+=c1
            else:res+="?"
        return res+b[w:]

    ss=[SI() for _ in range(3)]
    ans=len(ss[0])+len(ss[1])+len(ss[2])
    for i in range(3):
        for j in range(3):
            if i==j:continue
            a,b=ss[i],ss[j]
            c = ss[3 - i - j]
            for l in range(len(a)):
                ret=same(a,b,l)
                if ret!="NO":
                    ab=ret
                    break
            else:ab = a+b
            for ll in range(len(ab)):
                ret = same(ab, c, ll)
                if ret != "NO":
                    #print(ret)
                    ans = min(ans, len(ret))
                    break
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def search(w1, w2):
	i = p = 0
	n1 = len(w1)
	n2 = len(w2)
	while i < n1 and p < n2:
		if w1[i] == w2[p] or w1[i] == "?" or w2[p] == "?":
			i += 1
			p += 1
		elif p == 0:
			i += 1
		else:
			p = 0
		if i == n1:
			return p
	return p

from itertools import permutations
a=input()
b=input()
c=input()
s=len(a)+len(b)+len(c)
ans=1e9
for n1,n2,n3 in permutations((a,b,c),3):
	x=search(n1,n2)
	t=list(n1)
	tt=list(n2)
	if x:
		for i in range(x):
			if not t[-i-1]=="?":
				tt[i]=t[-i-1]
	tt="".join(tt)
	y=search(tt,n3)
	ans=min(ans,s-x-y)
	# print(n1,n2,n3,x,y)
print(ans)