Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03660 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
# 木グラフなので各プレイヤから近い点の個数を比べればよい

N = int(input())

edge = [[] for _ in range(N)]

for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a-1].append(b-1)  
  edge[b-1].append(a-1)  

INF = 10**18

d_fe = [INF]*N
d_sn = [INF]*N

d_fe[0] = 0
d_sn[N-1] = 0

def f(d,x):
  dx = d[x]
  for v in edge[x]:
    if d[v] == INF:
      d[v] = dx+1
      f(d,v)
      
f(d_fe,0)
f(d_sn,N-1)

black = 0
white = 0

for x in range(N):
  if d_fe[x] <= d_sn[x]:
    black += 1
  else:
    white += 1

answer = 'Fennec' if black > white else 'Snuke'
print(answer)

Buggy submission (verdict: Runtime Error):
# 木グラフなので各プレイヤから近い点の個数を比べればよい

N = int(input())

edge = [[] for _ in range(N)]

for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a-1].append(b-1)  
  edge[b-1].append(a-1)  

INF = 10**18

d_fe = [INF]*N
d_sn = [INF]*N

d_fe[0] = 0
d_sn[-1] = 0

def f(d,x):
  dx = d[x]
  for v in edge[x]:
    if d[v] == INF:
      d[v] = dx+1
      f(d,v)
      
f(d_fe,0)
f(d_sn,N-1)

black = 0
white = 0

for x in range(N):
  if d_fe[x] <= d_sn[x]:
    black += 1
  else:
    white += 1

answer = 'Fennec' if black > white else 'Snuke'
print(answer)
Problem p03665 (python)

Fixed submission:
N,P = map(int,input().split())
A = [int(x) for x in input().split()]

odd = sum(x&1 for x in A)

if odd:
  # どちらも半分ずつ
  answer = 2**(N-1)
else:
  answer = (2 ** N) * (1-P)

print(answer)

Buggy submission (verdict: Runtime Error):
N,P = int(input())
A = [int(x) for x in input().split()]

odd = sum(x&1 for x in A)

if odd:
  # どちらも半分ずつ
  answer = 2**(N-1)
else:
  answer = (2 ** N) * P

print(answer)
Problem p03667 (python)

Fixed submission:
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
XY = [tuple(int(x) for x in input().split()) for _ in range(M)]

def subscore_solution():
    from collections import Counter
    for x,y in XY:
        A[x-1] = y
        covered = [False] * (N+N+10)
        for key,cnt in Counter(A).items():
            for i in range(cnt):
                covered[max(0,key-i)] = True
        print(sum(not bl for bl in covered[1:N+1]))

counter = [0] * (N+1)
covered = [0] * (N+N+10)
for a in A:
    counter[a] += 1
    covered[a-counter[a]+1] += 1
magic = sum(x==0 for x in covered[1:N+1])

for i,y in XY:
    x = A[i-1]
    A[i-1] = y
    rem = x - counter[x] + 1
    counter[x] -= 1
    counter[y] += 1
    add = y - counter[y] + 1
    covered[rem] -= 1
    if 1<=rem<=N and covered[rem] == 0:
        magic += 1
    if 1<=add<=N and covered[add] == 0:
        magic -= 1
    covered[add] += 1
    print(magic)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
XY = [tuple(int(x) for x in input().split()) for _ in range(M)]

def subscore_solution():
    from collections import Counter
    for x,y in XY:
        A[x-1] = y
        covered = [False] * (N+N+10)
        for key,cnt in Counter(A).items():
            for i in range(cnt):
                covered[max(0,key-i)] = True
        print(sum(not bl for bl in covered[1:N+1]))

if N <= 200 and M <= 200:
    subscore_solution()
    exit()

raise Exception
Problem p03674 (python)

Fixed submission:
# 基本的に重複がない
# n+1Ck − (n+1)-(r-l+1)Ck−1

MOD = 10**9+7
U = 10**5 + 1

def power_mod(a,n):
  if n == 0:
    return 1
  x = (power_mod(a,n//2)**2)%MOD
  return x if n%2 == 0 else (a*x)%MOD

def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = [1]*(U+1)
fact_inv = [1]*(U+1)
make_fact(fact,fact_inv)

# 重複の起きる場所の間隔だけが問題
n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

for k in range(1,n+2):
  ans = comb(n+1,k) - comb(rest,k-1)
  ans %= MOD
  print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
import numba as nb

# 基本的に重複がない
# n+1Ck − (n+1)-(r-l+1)Ck−1

MOD = 10**9+7
U = 10**5 + 1

def power_mod(a,n):
  if n == 0:
    return 1
  x = (power_mod(a,n//2)**2)%MOD
  return x if n%2 == 0 else (a*x)%MOD

@nb.njit
def make_fact(fact,fact_inv):
  for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
  fact_inv[U] = power_mod(fact[U],MOD-2)
  for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

fact = np.ones(U+1,dtype = np.int64)
fact_inv = np.ones(U+1,dtype = np.int64)
make_fact(fact,fact_inv)

# 重複の起きる場所の間隔だけが問題
n = int(input())
A = [int(x) for x in input().split()]

memo = dict()
d = 0
for i,x in enumerate(A):
  if x in memo:
    d = i - memo[x]
    break
  memo[x] = i

rest = n-d

for k in range(1,n+2):
  ans = comb(n+1,k) - comb(rest,k-1)
  ans %= MOD
  print(ans)
Problem p03682 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = [set() for _ in range(N)]
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1].add((i2,d))
    
# csr形式に直す
indptr = []
indrow = []
value = []
ptr = 0
for i in range(N):
  indptr.append(ptr)
  for j,v in edge[i]:
    indrow.append(j)
    value.append(v)
    ptr += 1
indptr.append(ptr)
value = np.array(value,dtype=int)
graph = csr_matrix((value,indrow,indptr),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N,N))

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]
for key in [itemgetter(1), itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge[i1,i2] = d

edge = edge.tocsr()

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(edge, overwrite = True).astype(int)
answer = tree.sum()
print(answer)
Problem p03688 (python)

Fixed submission:
import sys
input = sys.stdin.readline

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]

x = min(A)
y = max(A)

if x == y:
    # 全員がnon-uniqueな色 or 全員がuniqueな色
    bl = (x <= N//2) or (x == N-1)
elif y != x + 1:
    bl = False
else:
    a = A.count(x)
    b = A.count(y)
    # a人：unique color
    # b人：non-unique color
    # b人でc種類あるとする
    c = y - a
    bl = (1 <= c <= b//2)

answer = 'Yes' if bl else 'No'
print(answer)

Buggy submission (verdict: Runtime Error):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = sorted(map(int, readline().split()))

def main(A):
    N = len(A)
    if A[0] == A[-1]:
        raise
        x = A[0]
        return x == N - 1 or 2 * x <= N
    if A[0] + 1 != A[-1]:
        return False
    a, b = A[0], A[-1]
    full = b
    unique = sum(x == a for x in A)
    return N - unique >= 2 * a

print('Yes' if main(A) else 'No')
Problem p03697 (python)

Fixed submission:
a,b = map(int,input().split())
x = a+b
print('error' if x >= 10 else x)

Buggy submission (verdict: Runtime Error):
a,b = map(input().split())
x = a+b
print('error' if x >= 10 else x)
Problem p03738 (python)

Fixed submission:
a = int(input())
b = int(input())

answer = ''
if a > b:
  answer = 'GREATER'
elif a == b:
  answer = 'EQUAL'
else:
  answer = 'LESS'

print(answer)

Buggy submission (verdict: Runtime Error):
a,b = map(int,input().split())

answer = ''
if a > b:
  answer = 'GREATER'
elif a == b:
  answer = 'EQUAL'
else:
  answer = 'LESS'

print(answer)
Problem p03746 (python)

Fixed submission:
import sys
input = sys.stdin.readline

from collections import deque

# 伸ばせる限り伸ばせば答

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

path = deque(AB[0])
visited = set(AB[0])

while True:
    x = path[0]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.appendleft(y)
            visited.add(y)
            update = True
            break
    if not update:
        break
while True:
    x = path[-1]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.append(y)
            visited.add(y)
            update = True
            break
    if not update:
        break

print(len(path))
print(*path)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from collections import deque

# 伸ばせる限り伸ばせば答

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

path = deque(AB[0])
visited = set(AB[0])

while True:
    x = path[0]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.appendleft(y)
            visited.add(y)
            update = True
            break
    if not update:
        break
while True:
    x = path[-1]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.append(y)
            visited.add(y)
            update = True
            break
    if not update:
        break

print(len(path))
print(*path)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

from collections import deque

# 伸ばせる限り伸ばせば答

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

path = deque(AB[0])
visited = set(AB[0])

while True:
    x = path[0]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.appendleft(y)
            visited.add(y)
            update = True
            break
    if update:
        continue
    x = path[-1]
    for y in graph[x]:
        if y not in visited:
            path.append(y)
            visited.add(y)
            update = True
            break
    if update:
        continue
    break

print(len(path))
print(*path)
Problem p03766 (python)

Fixed submission:
import sys
input = sys.stdin.readline

MOD = 10**9 + 7
N = int(input())

dp = [0] * (N+10)
dp_cum = [0] * (N+10)

dp[1] = N-1; dp_cum[1] = N-1
dp[2] = N-1; dp_cum[2] = 2*(N-1)
for n in range(3,N+1):
    dp[n] = dp[n-1] + dp_cum[n-3]
    dp_cum[n] = (dp_cum[n-1] + dp[n]) % MOD

answer = sum(dp[1:N])*N + dp[N] + 1
answer %= MOD
print(answer)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

MOD = 10**9 + 7
N = int(input())

dp = [0] * (N+1)
dp_cum = [0] * (N+1)

dp[1] = N-1; dp_cum[1] = N-1
dp[2] = N-1; dp_cum[2] = 2*(N-1)
for n in range(3,N+1):
    dp[n] = dp[n-1] + dp_cum[n-3]
    dp_cum[n] = (dp_cum[n-1] + dp[n]) % MOD

answer = sum(dp[1:N])*N + dp[-1] + 1
answer %= MOD
print(answer)
Problem p03773 (python)

Fixed submission:
a,b = map(int,input().split())
ans = (a+b)%24
print(ans)

Buggy submission (verdict: Runtime Error):
a,b = map(int,input())
ans = (a+b)%24
print(ans)
Problem p03782 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A = [x if x <= K else K + 1 for x in A]
A.sort()

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - A[x])
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A.sort()
A = [x if x <= K else K + 1 for x in A]

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - x)
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A.sort()
A = [x if x <= K else K + 1 for x in A]

mask = (1 << K) - 1

def test(x):
    # x 番目を抜いて
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - x)
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = right
print(answer)
Problem p03819 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_L[R-L+1].append(L)

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L in d_to_L[m]:
        R = L+m-1
        x = L
        while x <= M:
            tree[x] += 1
            x += x & (-x)
        x = R+1
        while x <= M:
            tree[x] -= 1
            x += x & (-x)
        long -= 1
    s = long
    for x in range(m,M+1,m):
        while x:
            s += tree[x]
            x -= x & (-x)
    answer[m] = s

print('\n'.join(map(str, answer[1:])))
Problem p03833 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
	        if i<N-1:
                ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)
Problem p03846 (python)

Fixed submission:
# そもそも人数分布は一意。
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = np.array([int(x) for x in input().split()])

left = np.arange(N)
right = N-1-left
cnt_1 = np.bincount(np.abs(left-right))
cnt_2 = np.bincount(A)

if cnt_1.shape != cnt_2.shape or (cnt_1 != cnt_2).any():
  answer = 0
else:
  answer = pow(2, N//2, MOD)
  
print(answer)

Buggy submission (verdict: Runtime Error):
# そもそも人数分布は一意。
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = np.array([int(x) for x in input().split()])

left = np.arange(N)
right = N-1-left
cnt_1 = np.bincount(np.abs(left-right))
cnt_2 = np.bincount(A)

if (cnt_1 != cnt_2).any():
  answer = 0
else:
  answer = pow(2, N//2, MOD)
  
print(answer)
Problem p03854 (python)

Fixed submission:
S = input()

while True:
  if S[-5:] == 'dream':
    S = S[:-5]
    continue
  elif S[-7:] == 'dreamer':
    S = S[:-7]
    continue
  elif S[-5:] == 'erase':
    S = S[:-5]
    continue
  elif S[-6:] == 'eraser':
    S = S[:-6]
    continue
  break

answer = 'YES' if not S else 'NO'
print(answer)

Buggy submission (verdict: Runtime Error):
S = input()

while True:
  if S[-5:] == 'dream':
    S = S[:-5]
    continue
  elif S[:-7] == 'dreamer':
    S = S[:-7]
    continue
  elif S[-5:] == 'erase':
    S = S[:-5]
    continue
  elif S[-7:] == 'eraser':
    S = S[:-7]
    continue
  break

answer = 'YES' if not S else 'NO
print(answer)
Problem p03861 (python)

Fixed submission:
a,b,c = map(int,input().split())

ans = b//c - (a-1)//c
print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c = map(int,input())

ans = b//c - (a-1)//c
print(ans)
Problem p03866 (python)

Fixed submission:
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = np.empty((3,N+2),dtype=np.int64)
XYR[:,:2] = [[xs,xt],[ys,yt],[0,0]]

XYR[:,2:] = np.array([input().split() for _ in range(N)], dtype=np.int64).T

X,Y,R = XYR

dist = np.sqrt(np.square(X[:,None] - X[None,:]) + np.square(Y[:,None] - Y[None,:])) # euclid
dist -= R[:,None] + R[None,:]
np.maximum(dist, 0, out = dist)
dist[range(N+2), range(N+2)] = np.inf

graph = csgraph_from_dense(dist, null_value = np.inf)

answer = dijkstra(graph, indices = 0)[1]

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import *

xs,ys,xt,yt = map(int,input().split())
N = int(input())
XYR = np.empty((3,N+2),dtype=np.int64)
XYR[:,:2] = [[xs,xt],[ys,yt],[0,0]]

XYR[:,2:] = np.array([input().split() for _ in range(N)], dtype=np.int64).T

X,Y,R = XYR

dist = np.sqrt(np.square(X[:,None] - X[None,:]) + np.square(Y[:,None] - Y[None,:])) # euclid
dist -= R[:,None] + R[None,:]
np.maximum(dist, 0, out = dist)
dist[range(N+2), range(N+2)] = np.inf

graph = csgraph_from_dense(dist, null_value = np.inf)

answer = dijkstra(graph, indices = 0)[1]

print(answer)
Problem p03887 (python)

Fixed submission:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

"""
・2,3^n,2
・3(1)
・1
・333
"""

import numpy as np

MOD = 10**9 + 7

N,A,B,C = map(int,readline().split())

if B&1:
    print(0)
    exit()

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 10**5
x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

"""
・2,3^n,2：B2個
・3113：A-n個
・11：n個
・333333：m個
"""

B2 = B//2

answer = 0
for m in range(C//3+1):
    if B2 == 0:
        a = C-3*m; b = m; c = A-a
        if a < 0 or c < 0:
            continue
        x = fact[a+b+c] * fact_inv[a] % MOD
        x *= fact_inv[b]; x %= MOD
        x *= fact_inv[c]; x %= MOD
        answer += x
        continue
    n_min = max(0,A-C+3*m)
    # (B2+A+m)! / (B2)!(A-n)!(n)!(m)!
    x = fact[B2+A+m] * fact_inv[m] % MOD * fact_inv[B2] % MOD
    x *= fact_inv[A-n_min::-1]; x %= MOD
    x *= fact_inv[n_min:A+1]; x %= MOD
    # 2,3^n,2のところの3の振り分けを決める。B2個の非負整数の和がC-3m-(A-n)
    # (B2+A+m)! / (B2)!(A-n)!(n)!(m)!
    y = fact[B2-1+C-3*m-A+n_min:B2+C-3*m] * fact_inv[B2-1] % MOD
    y *= fact_inv[C-3*m-A+n_min:C-3*m+1]; y %= MOD
    answer += (x*y%MOD).sum()

answer %= MOD

print(answer)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

"""
・2,3^n,2
・3(1)
・1
・333
"""

import numpy as np

MOD = 10**9 + 7

N,A,B,C = map(int,readline().split())

if B&1:
    print(0)
    exit()

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

U = 10**5
x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

"""
・2,3^n,2：B2個
・3113：A-n個
・11：n個
・333333：m個
"""

B2 = B//2

answer = 0
for m in range(C//3+1):
    n_min = max(0,A-C+3*m)
    # (B2+A+m)! / (B2)!(A-n)!(n)!(m)!
    x = fact[B2+A+m] * fact_inv[m] % MOD * fact_inv[B2] % MOD
    x *= fact_inv[A-n_min::-1]; x %= MOD
    x *= fact_inv[n_min:A+1]; x %= MOD
    # 2,3^n,2のところの3の振り分けを決める。B2個の非負整数の和がC-3m-(A-n)
    # (B2+A+m)! / (B2)!(A-n)!(n)!(m)!
    y = fact[B2-1+C-3*m-A+n_min:B2+C-3*m] * fact_inv[B2-1] % MOD
    y *= fact_inv[C-3*m-A+n_min:C-3*m+1]; y %= MOD
    answer += (x*y%MOD).sum()

answer %= MOD

print(answer)