Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*pow(10,i,13)%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*pow(10,i,13)%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
print(dp[-1][5])

Fixed submission:
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*pow(10,i)%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*pow(10,i)%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
print(dp[-1][5])

Fixed submission:
"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200000)

mod = 10**9 +7
N,K = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)


def dfs(cur,p,nei):
    #curにいる状態で、選べる色がcandi通りある場合の、塗り方の場合の数。
    #pが親,neiがcurの距離2以下のノードの数（curの子、弟ノードは除く）。neiが0,1のとき子に渡すneiはnei+1+兄の数、
    # neiが2のとき、子に渡すneiは、2+兄の数。
    res = K-nei 
    nxnei = min(nei+1,2)
    for nx in edges[cur]:
        if nx != p:
            res = res * dfs(nx,cur,nxnei) % mod
            nxnei += 1
    return res

print(dfs(1,0,0))

Fixed submission:
import sys
sys.setrecursionlimit(200000)

mod = 10**9 +7
N,K = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)


def dfs(cur,p,nei):
    #curにいる状態で、選べる色がcandi通りある場合の、塗り方の場合の数。
    #pが親,neiがcurの距離2以下のノードの数（curの子、弟ノードは除く）。neiが0,1のとき子に渡すneiはnei+1+兄の数、
    # neiが2のとき、子に渡すneiは、2+兄の数。
    res = K-nei 
    nxnei = min(nei+1,2)
    for nx in edges[cur]:
        if nx != p:
            res = res * dfs(nx,cur,nxnei) % mod
            nxnei += 1
    return res

print(dfs(1,0,0))
Buggy python submission (verdict: Runtime Error):
"""
最短距離が2であるようなノードの組み合わせは、最高で(N-1)C2個存在する。
そこで、この(N-1)C2個の組み合わせがある状態をデフォルトとして、K個になるまで辺を増やしていく。
"""
import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
N,K = map(int,input().split())
if K > choose(N-1,2):
    print(-1)
else:
    edges = []
    for i in range(2,N+1):
        edges.append((1,i))
    rest = choose(N-1,2) - K
    for i in range(2,N+1):
        for j in range(i+1,N+1):
            if rest == 0:
                break
            else:
                edges.append((i,j))
                rest -= 1
        else:
            continue
        break
    print(len(edges))
    for u,v in edges:
        print(" ".join([str(u),str(v)]))


Fixed submission:
"""
Nの制約数の少なさてきに、全探索するのがよさそう。
とはいえ、ありうるすべてのグラフパターンを全探索したら、2**(N^2)かかる

N本目以降は、辺の数を増やせば増やすほど、有効なペアの数が減っていく。
逆にいうと、ペアの数を減らしたい場合は、N本目以降を追加する
"""
N,K = map(int,input().split())
if K > N*(N-1)//2-(N-1):
    print(-1)
    exit()
edges = []
base = 1
for i in range(base+1,N+1):
    edges.append(" ".join([str(base),str(i)]))

diff = (N-1)*(N-2)//2 - K
base = 2
while diff:
    for i in range(base+1,N+1):
        if diff == 0:
            break
        else:
            edges.append(" ".join([str(base),str(i)]))
            diff -= 1
    base += 1
print(len(edges))
for ans in edges:
    print(ans)
Buggy python submission (verdict: Runtime Error):

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: -x[1])
A.sort()
cur = 0
for b,c in BC:
    while b > 0:
        b -= 1
        if A[cur] < c:
            A[cur] = c
            cur += 1
        else:
            break
    else:
        continue
    break
print(sum(A))


Fixed submission:
"""
カードの中から値がC未満のものをB枚までCに変更していく。これを高速に行えばよい。
heapqにぶち込めばよさそう?いや、それだとO(NMlogN)かかる
BIT使えばよいのか？いや、それもダメO(10**9log10**9)かかる
1クエリに対して、logN以下で処理しなくてはいけない。
Aを昇順に並べ替えておいて、常に昇順が保たれるようにしておけば二分探索できる。
あーでも途中で値を更新する作業があるから結局O(MN)かかるな
そもそも値を配列で管理してはいけないんだな。
どの値がいくつある。という管理の仕方をしないといけない。
ってなると、座標圧縮してBITだな。これはムズイわ。
"""
class BIT:
    def __init__(self,n):
        self.tree = [0]*(n+1)
        self.size = n

    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
    
    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: -x[1])

for b,c in BC:
    while b > 0:
        b -= 1
        a = heapq.heappop(A)
        if a < c:
            heapq.heappush(A,c)
        else:
            heapq.heappush(A,a)
            break
    else:
        continue
    break
print(sum(A))
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
digit = 'zero padding: {:0=6}'
dic = [[] for _ in range(N+1)]

for i in range(M):
    p,y = map(int,input().split())
    dic[p].append((y,i))

for p in dic:
    p.sort()

ans = [None for _ in range(M)]
for k in range(M):
    p = dic[k]
    for j in range(len(p)):
        i = p[j][1]
        ID = str(k).zfill(6)+str(j+1).zfill(6)
        ans[i] = ID

for a in ans:
    print(a)

Fixed submission:
N,M = map(int,input().split())
digit = 'zero padding: {:0=6}'
dic = [[] for _ in range(N+1)]

for i in range(M):
    p,y = map(int,input().split())
    dic[p].append((y,i))

for p in dic:
    p.sort()

ans = [None for _ in range(M)]
for k in range(1,N+1):
    p = dic[k]
    for j in range(len(p)):
        i = p[j][1]
        ID = str(k).zfill(6)+str(j+1).zfill(6)
        ans[i] = ID

for a in ans:
    print(a)
Buggy python submission (verdict: Runtime Error):
"""
---アルゴリズム概要---
Mを構成する素因数を、a1~aNの各スロットにいくつ置くのか、を考える問題。
まずは試し割りによってMを素因数分解。
重複組合せの公式で各素因数の配置パターンを算出し累乗していく。

試し割りは、O(√M)の計算量で処理できる。
√Mを超える素因数は、多くても一つしか存在しないため、√Mを超える値で試し割りをする必要はない。
もし√Mまでの値で試し割りを終えた段階で、Mを素因数分解しきれていなければ、残った商こそが√Mを超える唯一の素因数である。

簡単に証明
もし√Mを超える素因数が２つ存在しているとしよう。
それらは、(√M + α)と(√M + β)というふうに表すことができる。
この２つの積は明らかにMの値を超えてしまう。つまり前提に矛盾する。
したがって、√Mを超える素因数は多くても一つ
"""
from collections import Counter
import math

N,M = map(int,input().split())
factors = []

while M%2 == 0:
    M//=2
    factors.append(2)
    
f = 3
while f**2 <= M:
    while M%f==0:
        M//=f
        factors.append(f)
    f+=2
if M!=0:
    factors.append(M)

factors = Counter(factors)

ans = 1
for k in factors.values():
    ans *= math.factorial(k+N-1)//(math.factorial(N-k)*math.factorial(k))

print(ans%(10**9+7))

Fixed submission:
def main():
    import math
    from collections import Counter

    N,M = map(int,input().split())
    a = []
    def prime_factorize(n):
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a
    prime_factorize(M)
    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    divisors = Counter(a)
    count = 1
    for k,v in divisors.items():
        count *= combinations_count(v+N-1,v)

    print(count%(10**9+7))
main()
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
ts = [list(map(int,input().split()))[::-1]]

count += 0
t = 0

for i in range(m):
  if ts[i][1]>=t:
    count+=1
    t = ts[i][0]
    
print(count)

Fixed submission:
n,m = map(int,input().split())
ts = [list(map(int,input().split()))[::-1] for j in range(m)]

ts.sort()

count = 0
t = 0

for j in range(m):
  if ts[j][1]>=t:
    count+=1
    t = ts[j][0]
    
print(count)
Buggy python submission (verdict: Runtime Error):
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
def main():
    import sys
    input = sys.stdin.readline
    import heapq
    n,m,s,t = map(int,input().split())
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))

    yenEdges = [[] for _ in range(n+1)]
    snuukEdges = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        yenEdges[u].append((v,a))
        yenEdges[v].append((u,a))
        snuukEdges[u].append((v,b))
        snuukEdges[v].append((u,b))
    yenDic = {}
    snuukDic = {}

    dijkstra(yenEdges,yenDic,s)
    dijkstra(snuukEdges,snuukDic,t)

    remainingSnuuk = []
    for i in range(1,n+1):
        remainingSnuuk.append((10**15-(yenDic[i]+snuukDic[i])),i)
    remainingSnuuk.sort(key=lambda x: x[0], reverse=True)

    j = 0
    for i in range(n):
        while remainingSnuuk[j][1] <= i:
            j += 1
        print(remainingSnuuk[j][0])
main()

Fixed submission:
import heapq

n,m,s,t = map(int,input().split())
edgesYen = [[]for _ in range(n+1)]
edgesSnuuk = [[]for _ in range(n+1)]

for _ in range(m):
    u,v,a,b = map(int,input().split())
    edgesYen[u].append((v,a))
    edgesYen[v].append((u,a))
    edgesSnuuk[u].append((v,b))
    edgesSnuuk[v].append((u,b))


def dijkstra(edges,costDic,que):
    while que:
        cost,now = heapq.heappop(que)
        if now not in costDic:
            costDic[now] = cost
            for nx,c in edges[now]:
                if nx not in costDic:
                    heapq.heappush(que,(cost+c,nx))
#都市sから各都市に円で行く場合の最小コストを求める。
costYen = {}
que1 = [(0,s)]
heapq.heapify(que1)
dijkstra(edgesYen,costYen,que1)

costSnuuk = {}
que2 = [(0,t)]
heapq.heapify(que2)
dijkstra(edgesSnuuk,costSnuuk,que2)


minimumCosts = []
for i in range(1,n+1):
    cost = costYen[i] + costSnuuk[i]
    minimumCosts.append((cost,i))
heapq.heapify(minimumCosts)

money = 10**15
tmp = heapq.heappop(minimumCosts)
for i in range(n):
    while tmp[1] <= i:
        tmp = heapq.heappop(minimumCosts)
    print(money-tmp[0])
Buggy python submission (verdict: Runtime Error):
"""

Wは100で固定する。
1行目でできるかぎり連結成分の数が多くなるようにする。


W=100で固定し、白黒格子上になるように列を組む。
白と黒どちらかが規定数をオーバーしたら次の行で調整を入れて数を減らす。
ここでは、白が規定数に達したと仮定しよう。
白色の数に調整を入れたら、次の行では
"""
A,B = map(int,input().split())
N = 10
n = N//2
grid = [["#"]*N for _ in range(N)]
for i in range(N//2,N):
    for j in range(N):
        grid[i][j] = "."

A -= 1
B -= 1

for i in range(0,A//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "."

for j in range(0,A%n*2,2):
    grid[A//n*2][j] = "."

grid = grid[::-1]
for i in range(0,B//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "#"

for j in range(0,B%n*2,2):
    grid[B//n*2][j] = "#"

print(grid)

Fixed submission:
"""

Wは100で固定する。
1行目でできるかぎり連結成分の数が多くなるようにする。


W=100で固定し、白黒格子上になるように列を組む。
白と黒どちらかが規定数をオーバーしたら次の行で調整を入れて数を減らす。
ここでは、白が規定数に達したと仮定しよう。
白色の数に調整を入れたら、次の行では
"""
A,B = map(int,input().split())
N = 100
n = N//2
grid = [["#"]*N for _ in range(N)]
for i in range(n,N):
    for j in range(N):
        grid[i][j] = "."

A -= 1
B -= 1

for i in range(0,A//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "."

for j in range(0,A%n*2,2):
    grid[A//n*2][j] = "."

grid = grid[::-1]
for i in range(0,B//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "#"

for j in range(0,B%n*2,2):
    grid[B//n*2][j] = "#"

print(" ".join([str(N),str(N)]))
for i in range(N):
    print("".join(grid[i]))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
M = int(input())
T = Counter([input() for _ in range(M)])
G = S-T
print(max([a for a in G.values()]))

Fixed submission:
from collections import Counter
N = int(input())
blue = []
for _ in range(N):
    blue.append(input())
blue = Counter(blue)

M = int(input())
red = []
for _ in range(M):
    red.append(input())
red = Counter(red)

diff = blue - red
if len(diff)==0:
    print(0)
else:
    print(max(diff.values()))
Buggy python submission (verdict: Time Limit Exceeded):
X,Y = map(int,input().split())
count = 1

while True:
  if X*2 <= Y:
    count +=1
    X = X*2
    
print(count)

Fixed submission:
import math

x,y = map(int,input().split())
"""
値をどんどん2倍していって、それがyを超えないかを検証し、越えなければカウントを増やす
"""

count = 0
origin = x
while True:
  if origin <= y:
    count+=1
    origin = origin * 2
  else:
    break
    
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from bisect import bisect
    import sys
    sys.setrecursionlimit(200000)

    N = int(input())
    A = sorted(list(map(int,input().split())))
    B = sorted(list(map(int,input().split())))
    C = sorted(list(map(int,input().split())))
    ans = 0
    for a in A:
        bIdx = bisect(B,a)
        if N - bIdx > 0:
            for j in range(bIdx,N):
                b = B[j]
                cIdx = bisect(C,b)
                if N - cIdx > 0:
                    ans += N-cIdx

    print(ans)
main()

Fixed submission:
"""
前処理で下記のようなメモを作っておく必要がある。
candidate[j] -> 昇順ソートされたBの中でインデックスj以降のパーツを使えるときに、考えられるB,Cの組み合わせの数。
candidateリストを作成するためにまずは、下記のmemoを用意して、その総和としてcandidateを作成する。
memo[j] -> Bの中のインデックスjのパーツを使った場合に使用可能なCの数。
"""

def main():
    from bisect import bisect
    import sys
    sys.setrecursionlimit(200000)

    N = int(input())
    A = sorted(list(map(int,input().split())))
    B = sorted(list(map(int,input().split())))
    C = sorted(list(map(int,input().split())))

    memo = [0]*(N)
    for j in range(N):
        b = B[j]
        cIdx = bisect(C,b)
        memo[j] = N-cIdx
    candidate = [0]*(N)
    candidate[-1] = memo[-1]
    for j in range(N-2,-1,-1):
        candidate[j] += candidate[j+1]+memo[j]

    ans = 0
    for a in A:
        bIdx = bisect(B,a)
        if bIdx < N:
            ans += candidate[bIdx]

    print(ans)
main()

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect

N = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))
ans = 0
for a in A:
    bIdx = bisect(B,a)
    if N - bIdx > 0:
        for j in range(bIdx,N):
            b = B[j]
            cIdx = bisect(C,b)
            if N - cIdx > 0:
                ans += N-cIdx

print(ans)


Fixed submission:
"""
前処理で下記のようなメモを作っておく必要がある。
candidate[j] -> 昇順ソートされたBの中でインデックスj以降のパーツを使えるときに、考えられるB,Cの組み合わせの数。
candidateリストを作成するためにまずは、下記のmemoを用意して、その総和としてcandidateを作成する。
memo[j] -> Bの中のインデックスjのパーツを使った場合に使用可能なCの数。
"""

def main():
    from bisect import bisect
    import sys
    sys.setrecursionlimit(200000)

    N = int(input())
    A = sorted(list(map(int,input().split())))
    B = sorted(list(map(int,input().split())))
    C = sorted(list(map(int,input().split())))

    memo = [0]*(N)
    for j in range(N):
        b = B[j]
        cIdx = bisect(C,b)
        memo[j] = N-cIdx
    candidate = [0]*(N)
    candidate[-1] = memo[-1]
    for j in range(N-2,-1,-1):
        candidate[j] += candidate[j+1]+memo[j]

    ans = 0
    for a in A:
        bIdx = bisect(B,a)
        if bIdx < N:
            ans += candidate[bIdx]

    print(ans)
main()
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
lenS = len(S)
lenT = len(T)
ans = ""
for i in range(lenS-lenT,-1,-1):
    for j in range(lenT):
        if S[i+j]!=T[j] and S[i+j]!="?":
            break
    else:
        ans = S[:i]+T+S[i+lenT:]
        ans = ans.replace("?","a")
        print(ans)
        sys.exit()
print("UNRESTORABLE")

Fixed submission:
import sys

s = input()
t = input()

for i in range(len(s)-len(t)+1):
  if i == 0:
    sub = s[-i-len(t):]
  else:
    sub = s[-i-len(t):-i]
  for j in range(len(t)):
    if sub[j]!=t[j] and sub[j]!="?":
      break
  else:
    if i == 0:
      s = s[:-i-len(t)]+t
    else:
      s = s[:-i-len(t)]+t+s[-i:]
    s = s.replace("?","a")
    print(s)
    sys.exit()
  continue
    
print("UNRESTORABLE")

Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

tLen = len(t)

"""
sの中の?を.に置換する
"""
s.replace("?",".")

print(s)

for i in range(tLen,len(s)+1):
  #[-i:(-i+tLen)]の区間の文字列が、tにマッチするかを調べる。マッチするなら置換する。

Fixed submission:
import sys

s = input()
t = input()

for i in range(len(s)-len(t)+1):
  if i == 0:
    sub = s[-i-len(t):]
  else:
    sub = s[-i-len(t):-i]
  for j in range(len(t)):
    if sub[j]!=t[j] and sub[j]!="?":
      break
  else:
    if i == 0:
      s = s[:-i-len(t)]+t
    else:
      s = s[:-i-len(t)]+t+s[-i:]
    s = s.replace("?","a")
    print(s)
    sys.exit()
  continue
    
print("UNRESTORABLE")
Buggy python submission (verdict: Runtime Error):
from itertools import permutations
N,M,R = map(int,input().split())
RList = list(map(int,input().split()))
dp = [[[float("INF")]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
for i in range(N+1):
    dp[i][i] = 0
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[a][b] = c
    dp[b][a] = c

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            dp[j][k] = min(dp[j][i]+dp[i][k],dp[j][k])

ans = float("INF")
RList = list(permutations(RList))
for Rs in RList:
    tmp = 0
    for i in range(1,R):
        a = Rs[i-1]
        b = Rs[i]
        tmp += dp[a][b]
    ans = min(ans,tmp)
print(ans)

Fixed submission:
N,M,r = map(int,input().split())
R = list(map(int,input().split()))
#dp[i][j][k] -> 町iまで経由地点として使える。j,kの最短移動距離
dp = [[float("INF")]*(N+1) for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().split())
    dp[a][b] = c
    dp[b][a] = c

for i in range(N+1):
    dp[i][i] = 0

for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(N+1):
            dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

from itertools import permutations
ans = float("INF")
for pattern in permutations(R):
    cost = 0
    for i in range(r-1):
        cost += dp[pattern[i]][pattern[i+1]]
    ans = min(ans,cost)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
T = [int(input()) for _ in range(N)]
def gcd(a,b):
    if b:
        return gcd(b,a%b)
    else:
        return a

def lcm(a,b):
    g = gcd(a,b)
    return a*b//g

l = lcm(T[0],T[1])
for i in range(2,N):
    l = lcm(l,T[i])

print(l)

Fixed submission:
"""
すべての秒数の最小公倍数を求める
Gを最大公約数として持つX,Yの最小公倍数はG*X/G*Y/G
"""
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
N = int(input())
T = [int(input()) for _ in range(N)]
tmp = T[0]
for i in range(1,N):
    t = T[i]
    g = gcd(tmp,t)
    tmp = g*(tmp//g)*(t//g)
print(tmp)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000)
N = int(input())
T = [int(input()) for _ in range(N)]
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

def lcm(a,b):
    g = gcd(a,b)
    return a*b//g

l = lcm(T[0],T[1])
for i in range(2,N):
    l = lcm(l,T[i])
print(l)

Fixed submission:
"""
すべての秒数の最小公倍数を求める
Gを最大公約数として持つX,Yの最小公倍数はG*X/G*Y/G
"""
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
N = int(input())
T = [int(input()) for _ in range(N)]
tmp = T[0]
for i in range(1,N):
    t = T[i]
    g = gcd(tmp,t)
    tmp = g*(tmp//g)*(t//g)
print(tmp)

Buggy python submission (verdict: Runtime Error):
N = int(input())
T = [int(input()) for _ in range(N)]
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

def lcm(a,b):
    g = gcd(a,b)
    return a*b//g

l = lcm(T[0],T[1])
for i in range(2,N):
    l = lcm(l,T[i])
print(l)

Fixed submission:
"""
すべての秒数の最小公倍数を求める
Gを最大公約数として持つX,Yの最小公倍数はG*X/G*Y/G
"""
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
N = int(input())
T = [int(input()) for _ in range(N)]
tmp = T[0]
for i in range(1,N):
    t = T[i]
    g = gcd(tmp,t)
    tmp = g*(tmp//g)*(t//g)
print(tmp)

Buggy python submission (verdict: Runtime Error):
N = int(input())
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    g = gcd(a,b)
    return (a*b)//g

T = [int(input()) for _ in range(N)]
l = lcm(T[0],T[1])
for i in range(2,N):
    l = lcm(l,T[i])

print(l)


Fixed submission:
"""
すべての秒数の最小公倍数を求める
Gを最大公約数として持つX,Yの最小公倍数はG*X/G*Y/G
"""
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)
N = int(input())
T = [int(input()) for _ in range(N)]
tmp = T[0]
for i in range(1,N):
    t = T[i]
    g = gcd(tmp,t)
    tmp = g*(tmp//g)*(t//g)
print(tmp)