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:
a = list(input())
b = list(input())
c = list(input())
A, B, C = map(len, (a, b, c))
OFFSET = 4000
L = 8001
ab = [True] * L
ac = [True] * L
bc = [True] * L

for i in range(A):
    for j in range(B):
        if a[i] != b[j] and a[i] != '?' and b[j] != '?':
            ab[i - j + OFFSET] = False  # BをAからi-jずらした時を考える

for i in range(A):
    for j in range(C):
        if a[i] != c[j] and a[i] != '?' and c[j] != '?':
            ac[i - j + OFFSET] = False  # CをAからi-jずらした時を考える

for i in range(B):
    for j in range(C):
        if b[i] != c[j] and c[i] != '?' and b[j] != '?':
            bc[i - j + OFFSET] = False  # CをBからi-jずらした時を考える

ans = float('inf')
for i in range(L):  # Bの左端をずらす
    for j in range(L):  # Cの左端をずらす
        k = j - i + OFFSET
        if k >= L or k < 0:
            continue
        if ab[i] and ac[j] and bc[k]:
            head = min(i, j, OFFSET)
            tail = max(A + OFFSET, B + i, C + j)
            ans = min(ans, tail - head)

print(ans)

Submission status: Runtime Error

Solution code:
a = list(input())
b = list(input())
c = list(input())
A, B, C = map(len, (a, b, c))
OFFSET = 7
L = 15
ab = [True] * L
ac = [True] * L
bc = [True] * L

for i in range(A):
    for j in range(B):
        if a[i] != b[j] and a[i] != '?' and b[j] != '?':
            ab[i - j + OFFSET] = False # BをAからi-jずらした時を考える

for i in range(A):
    for j in range(C):
        if a[i] != c[j] and a[i] != '?' and c[j] != '?':
            ac[i - j + OFFSET] = False # CをAからi-jずらした時を考える

for i in range(B):
    for j in range(C):
        if b[i] != c[j] and c[i] != '?' and b[j] != '?':
            bc[i - j + OFFSET] = False # CをBからi-jずらした時を考える

ans = float('inf')
for i in range(L): # Bの左端をずらす
    for j in range(L): # Cの左端をずらす
        k = j - i + OFFSET
        if k >= L or k < 0:
            continue
        if ab[i] and ac[j] and bc[k]:
            head = min(i, j, OFFSET)
            tail = max(A + OFFSET, B + i, C + j)
            ans = min(ans, tail - head)

print(ans)

Submission status: Runtime Error

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

    def check(x, y):
        for i in range(len(x)):
            for j in range(len(x)-i):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                cnt = i
                break
        else:
            cnt = len(x)
        ans = x[:cnt]
        x_rest = x[cnt:]
        for i in range(max(len(x_rest), len(y))):
            if i >= len(x_rest):
                ans += y[i]
            elif i >= len(y):
                ans += x_rest[i]
            else:
                if x_rest[i] == "?":
                    ans += y[i]
                else:
                    ans += x_rest[i]
        return ans
    print(min([len(check(check(i, j), k)) for i, j, k in [
          (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]]))


main()

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
def check(xn,yn): #x=<y
    ly = len(yn)
    lx = len(xn)
    if lx > ly:
        x =yn
        y =xn
        aaa = lx
        lx = ly
        ly = aaa
    else:
        x = xn
        y = yn
    for k in range(ly-lx+1):
        flag = True
        for l in range(lx):
            if x[l] == y[l+k] or x[l] =='?' or y[l+k] == '?':
                continue
            else:
                flag = False
                break
        if flag ==True:
            return [y]
    
    for k in range(1,lx): #x y
        flag = True
        ans1 = 0
        for l in range(k,lx):
            if x[l] == y[l-k] or x[l] == '?' or y[l-k] == '?':
                continue
            else:
                flag = False
                break
        if flag ==True:
            ans1 = x[0:k] + y
            break

    for k in range(1,lx): #y x
        flag = True
        ans2 = 0
        for l in range(0,lx-k):
            if x[l] == y[-lx+l+k] or x[l] == '?' or y[-lx+l+k] == '?':
                continue
            else:
                flag = False
                break
        if flag ==True:
            ans2 = y + x[-k:]
            break
    
    if ans1 != 0 and ans2 ==0:
        return [ans1]
    elif ans1 == 0 and ans2 != 0:
        return [ans2]
    elif ans1 ==0 and ans2 == 0:
        return [0]
    else:
        l1 = len(ans1)
        l2 = len(ans2)
        if l1 < l2:
            return [ans1]
        elif l1 > l2:
            return [ans2]
        else:
            return [1,ans1,ans2]

ab = check(a,b)
ac = check(a,c)
bc = check(b,c)
lis = [[0],[0],[0],[0],[0],[0]]
if ab[0] == 0:
    ab = 0
elif ab[0] == 1:
    lis[0] = check(c,ab[1])
    lis[1] = check(c,ab[2])
else:
    lis[0] = check(c,ab[0]) 

if ac[0] == 0:
    ac = 0
elif ac[0] == 1:
    lis[2] = check(b,ac[1])
    lis[3] = check(b,ac[2])
else:
    lis[2] = check(b,ac[0]) 

if bc[0] == 0:
    bc = 0
elif bc[0] == 1:
    lis[4] = check(a,bc[1])
    lis[5] = check(a,bc[2])
else:
    lis[4] = check(a,bc[0])
ex =[]
for k in lis:
    if k[0] ==1:
        ex.append([k[1]])
        ex.append([k[2]])

lis = [k for k in lis if not (k ==[0] or k[0] ==1)]
lis = lis + ex
if lis ==[]:
    print(len(a) + len(b) +len(c))
else:
    ans = len(lis[0][0])
    for k in lis:
        if len(k[0]) < ans:
            ans = len(k[0])
    print(ans)

Submission status: Runtime Error

Solution code:
from itertools import *

def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge2(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b1, a_b2, a_b3  = map(list, [merge1(a,b), merge2(a,b), merge3(a,b)])
  a_b = {*a_b1, *a_b2, *a_b3}
  a_c1, a_c2, a_c3  = map(list, [merge1(a,c), merge2(a,c), merge3(a,c)])
  a_c = {*a_c1, *a_c2, *a_c3}
  b_c1, b_c2, b_c3  = map(list, [merge1(b,c), merge2(b,c), merge3(b,c)])
  b_c = {*b_c1, *b_c2, *b_c3}
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = (  
    chain(
      (lb+i for i in a_b2 if (a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2))),
      (lb+i for i in count(a_b2[-1]+1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2))),
    ),
    
    chain(
      (la-i for i in a_b3 if (b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3))),
      (la-i for i in count(a_b3[-1]-1, -1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3))),
    ),
    
    chain(
      (lc+i for i in a_c2 if (a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2))),
      (lc+i for i in count(a_c2[-1]+1) if any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2))),
    ),
    
    chain(
      (la-i for i in a_c3 if (a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3))),
      (la-i for i in count(a_c3[-1]-1, -1) if any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3))),
    ),
  )
  
  return min(map(next, can))

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

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
from itertools import *

def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge2(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb
  
def seq(*seqs):
  for merge
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b1, a_b2, a_b3  = map(list, [merge1(a,b), merge2(a,b), merge3(a,b)])
  a_b = {*a_b1, *a_b2, *a_b3}
  a_c1, a_c2, a_c3  = map(list, [merge1(a,c), merge2(a,c), merge3(a,c)])
  a_c = {*a_c1, *a_c2, *a_c3}
  b_c1, b_c2, b_c3  = map(list, [merge1(b,c), merge2(b,c), merge3(b,c)])
  b_c = {*b_c1, *b_c2, *b_c3}
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = (  
    chain(
      (lb+i for i in a_b2 if (a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2))),
      (lb+i for i in count(a_b2[-1]+1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2))),
    ),
    
    chain(
      (la-i for i in a_b3 if (b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3))),
      (la-i for i in count(a_b3[-1]-1, -1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3))),
    ),
    
    chain(
      (lc+i for i in a_c2 if (a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2))),
      (lc+i for i in count(a_c2[-1]+1) if any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2))),
    ),
    
    chain(
      (la-i for i in a_c3 if (a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3))),
      (la-i for i in count(a_c3[-1]-1, -1) if any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3))),
    ),
  )
  
  return min(map(next, can))

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

print(min_merge(a,b,c))

Submission status: Runtime Error

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

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 6000
    BC = [1] * 6000
    AC = [1] * 6000
    for i in range(-lb, la+1):
        lab = min(la, lb)
        AB[i] = check(A[max(0, i):min(lab, i+lb)], B[max(0, -i):min(lab, lb-i)])
    for i in range(-lc, lb+1):
        lbc = min(lb, lc)
        BC[i] = check(B[max(0, i):min(lbc, i+lc)], C[max(0, -i):min(lbc, lc-i)])
    for i in range(-lc, la+1):
        lca = min(la, lc)
        AC[i] = check(A[max(0, i):min(lca, i+lc)], C[max(0, -i):min(lca, lc-i)])

    ans = la+lb+lc
    for i in range(-lb-lc, la+lc+1):
        if not AB[i]:
            continue
        for j in range(-lc, lb+1):
            if BC[j] and AC[i+j]:
                l = min(0, i, i+j)
                r = max(la, lb+i, lc+i+j)
                #print(i, j, l, r, r-l)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>

using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define R pair<pair<int, int>, pair<int, int>>
#define S(i,j,k,l) mkp(mkp(i,j),mkp(k,l))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define req(n,i) for(int (i) = (n) - 1 ; (i) >= 0 ; (i)--)
#define range(i,v) for(auto& (i) : v)
#define mkp make_pair
#define mem(x,k) memset(x,k,sizeof(x))
#define vec vector
#define pb emplace_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) lower_bound(all(b),(i))-b.begin()
#define ssp(i,n) (i==n-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define itn int
#define pri_que priority_queue
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define pppp(x,y,z,w) pb(S(x,y,z,w))
#define cyes cout<<"Yes\n"
#define cno cout<<"No\n"
#define endl "\n"
constexpr int mod = 1e9 + 7;
constexpr int Mod = 998244353;
constexpr int MXN = 500000 + 100;
constexpr ll inf = 3 * 1e18;
constexpr int Inf = 15 * 1e8;
const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }
void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }
bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p = mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*constexpr int fn_ = 1000005;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++)
			fact_[i] = fact_[i - 1] * i % Mod;
		comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);
		for (int i = fn_ - 2; i > 0; i--)
			comp_[i] = comp_[i + 1] * (i + 1) % Mod;
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//--------------------------------------------------------------
bool ab[100000], ac[100000], bc[100000];
bool match(char c1, char c2) {
	return (c1 == '?' || c2 == '?' || c1 == c2);
}
string a, b, c;
signed main() {
	cin >> a >> b >> c;
	int A = a.size(), B = b.size(), C = c.size();
	rep(i, A)rep(j, B) if (!match(a[i], b[j])) ab[i - j + 50000] = true;
	rep(i, A)rep(j, C) if (!match(a[i], c[j])) ac[i - j + 50000] = true;
	rep(i, B)rep(j, C) if (!match(b[i], c[j])) bc[i - j + 50000] = true;
	int m = 2000;
	int ans = 3 * m;
	for (int i = -2 * m; i <= 2 * m; i++) for (int j = -2 * m; j <= 2 * m; j++) if (!ab[i + 50000] && !ac[j + 50000] && !bc[j - i + 50000]) {
		int l = min(0ll, min(i, j));
		int r = max(A, max(B + i, C + j));
		ans = min(ans, r - l);
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>

using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define R pair<pair<int, int>, pair<int, int>>
#define S(i,j,k,l) mkp(mkp(i,j),mkp(k,l))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define req(n,i) for(int (i) = (n) - 1 ; (i) >= 0 ; (i)--)
#define range(i,v) for(auto& (i) : v)
#define mkp make_pair
#define mem(x,k) memset(x,k,sizeof(x))
#define vec vector
#define pb emplace_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) lower_bound(all(b),(i))-b.begin()
#define ssp(i,n) (i==n-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define itn int
#define pri_que priority_queue
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define pppp(x,y,z,w) pb(S(x,y,z,w))
#define cyes cout<<"Yes\n"
#define cno cout<<"No\n"
#define endl "\n"
constexpr int mod = 1e9 + 7;
constexpr int Mod = 998244353;
constexpr int MXN = 500000 + 100;
constexpr ll inf = 3 * 1e18;
constexpr int Inf = 15 * 1e8;
const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }
void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }
bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p = mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*constexpr int fn_ = 1000005;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++)
			fact_[i] = fact_[i - 1] * i % Mod;
		comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);
		for (int i = fn_ - 2; i > 0; i--)
			comp_[i] = comp_[i + 1] * (i + 1) % Mod;
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//--------------------------------------------------------------
bool ab[100000], ac[100000], bc[100000];
bool match(char c1, char c2) {
	return (c1 == '?' || c2 == '?' || c1 == c2);
}
string a, b, c;
signed main() {
	cin >> a >> b >> c;
	int A = a.size(), B = b.size(), C = c.size();
	rep(i, A)rep(j, B) if (!match(a[i], b[j])) ab[i - j + 50000] = true;
	rep(i, A)rep(j, B) if (!match(a[i], c[j])) ac[i - j + 50000] = true;
	rep(i, B)rep(j, C) if (!match(b[i], c[j])) bc[i - j + 50000] = true;
	int m = 2000;
	int ans = 3 * m;
	for (int i = -2 * m; i <= 2 * m; i++) for (int j = -2 * m; j <= 2 * m; j++) if (!ab[i + 50000] && !ac[j + 50000] && !bc[j - i + 50000]) {
		int l = min(0ll, min(i, j));
		int r = max(A, max(B + i, C + j));
		ans = min(ans, r - l);
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>

using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define R pair<pair<int, int>, pair<int, int>>
#define S(i,j,k,l) mkp(mkp(i,j),mkp(k,l))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define req(n,i) for(int (i) = (n) - 1 ; (i) >= 0 ; (i)--)
#define range(i,v) for(auto& (i) : v)
#define mkp make_pair
#define mem(x,k) memset(x,k,sizeof(x))
#define vec vector
#define pb emplace_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) lower_bound(all(b),(i))-b.begin()
#define ssp(i,n) (i==n-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define itn int
#define pri_que priority_queue
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define pppp(x,y,z,w) pb(S(x,y,z,w))
#define cyes cout<<"Yes\n"
#define cno cout<<"No\n"
#define endl "\n"
constexpr int mod = 1e9 + 7;
constexpr int Mod = 998244353;
constexpr int MXN = 500000 + 100;
constexpr ll inf = 3 * 1e18;
constexpr int Inf = 15 * 1e8;
const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }
void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }
bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p = mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*constexpr int fn_ = 1000005;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++)
			fact_[i] = fact_[i - 1] * i % Mod;
		comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);
		for (int i = fn_ - 2; i > 0; i--)
			comp_[i] = comp_[i + 1] * (i + 1) % Mod;
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//--------------------------------------------------------------
bool ab[100000], ac[100000], bc[100000];
bool match(char c1, char c2) {
	return (c1 == '?' || c2 == '?' || c1 == c2);
}
signed main() {
	int i, j; string a, b, c;
	cin >> a >> b >> c;
	int A = a.size(), B = b.size(), C = c.size();
	rep(i, A)rep(j, B) if (!match(a[i], b[j])) ab[i - j + 50000] = true;
	rep(i, A)rep(j, B) if (!match(a[i], c[j])) ac[i - j + 50000] = true;
	rep(i, B)rep(j, C) if (!match(b[i], c[j])) bc[i - j + 50000] = true;
	int m = 2000;
	int ans = 3 * m;
	for (int i = -2 * m; i <= 2 * m; i++) for (int j = -2 * m; j <= 2 * m; j++) if (!ab[i + 50000] && !ac[j + 50000] && !bc[j - i + 50000]) {
		int l = min(0ll, min(i, j));
		int r = max(A, max(B + i, C + j));
		ans = min(ans, r - l);
	}
	cout << ans << endl;
}

Submission status: Runtime Error

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

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = max([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L2, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L2, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([0, i2, i3])+L1 - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))

Submission status: Runtime Error

Solution code:
from itertools import permutations
A = input()
B = input()
C = input()
abc = [A,B,C]
num = [0,1,2]
ans = 6000
for i,j,k in permutations(num):
    a = abc[i]
    b = abc[j]
    c = abc[k]
    for i in range(len(a)):
        flag = True
        for j in range(len(a)-i):
            if not (a[i+j] == b[j] or (a[i+j] == '?' or b[j] == '?')):
                flag = False
                break
        if flag:
            ab = a +b[j+1:]
            break
    if not flag:
        ab = a+b
    for i in range(len(ab)):
        flag = True
        for j in range(len(ab)-i):
            if not (ab[i+j] == c[j] or (ab[i+j] == '?' or c[j] == '?')):
                flag = False
                break
        if flag:
            abc1 = ab +c[j+1:]
            break
    if not flag:
        abc1 = ab+c
    ans = min(ans,len(abc1))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations
A = input()
B = input()
C = input()
abc = [A,B,C]
num = [0,1,2]
ans = 0
for i,j,k in permutations(num):
    a = abc[i]
    b = abc[j]
    c = abc[k]
    for i in range(len(a)):
        flag = True
        for j in range(len(a)-i):
            if not (a[i+j] == b[j] or (a[i+j] == '?' or b[j] == '?')):
                flag = False
                break
        if flag:
            ab = a +b[j+1:]
            break
    if not flag:
        ab = a+b
    for i in range(len(ab)):
        flag = True
        for j in range(len(ab)-i):
            if not (ab[i+j] == c[j] or (ab[i+j] == '?' or c[j] == '?')):
                flag = False
                break
        if flag:
            abc1 = ab +c[j+1:]
            break
    if not flag:
        abc1 = ab+c
    ans = max(ans,len(abc1))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import re

def chk(a,b,c):
      la = len(a)
      lb = len(b)
      lc = len(c)
      for x in range(0,la):
       xflag = 0
       for i in range(0,la-x):
         if not ( a[x+i] == b[i] or a[x+i] == '?' or b[i] == '?'):
           xflag=1
           break
       if(xflag == 0):
         startb = i
         for y in range(0,lb):
           yflag = 0
           for j in range(0,lb-y):
             if not ( b[y+j] == c[j] or b[y+j] == '?' or c[j] == '?'):
               yflag=1
               break
           if(yflag == 0):
             startc = j
             if(la > x+y):
               for z in range(0,la):
                 zflag = 0
                 for k in range(0,la-z):
                   if not ( a[x+k] == c[k] or a[x+k] == '?' or a[k] == '?'):
                     zflag=1
                     break
                 if(zflag == 0):
                   dummy = k
                   ret = len(a[0:x] + b[0:y] + c[z:])
                   return(ret) 
             else:
               ret = len(a[0:x] + b[0:y] + c[0:])
               return(ret) 
      return(0)


za = sys.stdin.readline().replace('\n','')
zb = sys.stdin.readline().replace('\n','')
zc = sys.stdin.readline().replace('\n','')

ret = chk(za,zb,zc)
if( ret != 0):
  print(ret)
  exit(0)
ret = chk(za,zc,zb)
if( ret != 0):
  print(ret)
  exit(0)
ret = chk(zb,za,zc)
if( ret != 0):
  print(ret)
  exit(0)
ret = chk(zb,zc,zb)
if( ret != 0):
  print(ret)
  exit(0)
ret = chk(zc,za,zb)
if( ret != 0):
  print(ret)
  exit(0)
ret = chk(zc,zb,za)
if( ret != 0):
  print(ret)
  exit(0)
sys.stdout.flush()