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

Fixed submission:
N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Buggy submission (verdict: Runtime Error):
N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#頂点xから伸びる部分木に含まれる頂点の個数のリストを返す
def get_sub_tree_node_nums(x):
    ret=[]
    used=[False]*N
    used[x]=True
    for s in E[x]:
        n=1
        stack=[s]
        used[s]=True
        while stack:
            node=stack.pop()
            for ss in E[node]:
                if not used[ss]:
                    stack.append(ss)
                    n+=1
                    used[ss]=True
        ret.append(n)
    return ret

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in range(N):
        p=0
        subnodes = get_sub_tree_node_nums(i)
        if len(subnodes)>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in subnodes:
                p1+=(1<<s)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2[1]%MOD
        ans+=p
        ans%=MOD
    print(ans)

solve()
Problem p02837 (python)

Fixed submission:
N = int(input())
A = []
for _ in range(N):
    a = int(input())
    xy = []
    for __ in range(a):
        xy.append(tuple(map(int,input().split())))
    A.append(xy)

ok = []
for i in range(2**N):
    v = [0] * (N+1)
    n = i
    for j in range(1, N+1):
        v[j] = n % 2
        n >>= 1
    for k, xys in enumerate(A):
        if v[k+1] == 1:
            for xy in xys:
                if xy[1] != v[xy[0]]:
                    break
            else:
                continue
            break
    else:
        ok.append(v)

ans = 0
for a in ok:
    ans = max(ans,sum(a))
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
xy=[[] for in range(N)]
for _ in range(N):
    A = int(input())
    for __ in range(A):
        x, y = map(int, input().split())
        xy[_].append((x-1,y))

ans = 0
for p in range(1<<N):
    h = []
    judge = True
    for i in range(N):
        h.append(p&1)
        p>>=1
    for i in range(N):
        for x, y in xy[i]:
            if h[i] and y != h[x]:
                judge = False
                break
        if not judge: break
    if not judge: continue
    ans = max(ans,sum(h))

print(ans)
Problem p02939 (python)

Fixed submission:
S = input()
before = ""

count = 0
i = 0
while i < len(S):
    for l in range(1, len(S) - i):
       if S[i:i+l] != before and S[i:i+l] != S[i+l:]:
           count += 1
           before = S[i:i+l]
           break
    i += l

print(count+1)

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

def divide_str_to_list(s, before):
    for i in range(1, len(s)):
        if s[0:i] != before and s[i:] != s[0:i]:
            return 1 + divide_str_to_list(s[i:], s[0:i])
    return 1

print(divide_str_to_list(S, ""))

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

def divide_str_to_list(s, before):
    for i in range(1, len(s)):
        if s[0:i] != before and s[i:] != s[0:i]:
            return [s[0:i]] + divide_str_to_list(s[i:], s[0:i])
    return [s]

print(len(divide_str_to_list(S, "")))
Problem p03000 (python)

Fixed submission:
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 1
d = 0
for l in L:
    if d + l <= X:
        ans += 1
        d += l
    else:
        break
print(ans)

Buggy submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 0
d = 0
while ans < N and d <= X:
    ans += 1
    d += L[ans]
if d <= X:
    ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
N, X = map(int, input().split())
*L, = map(int, input().split())
ans = 0
d = 0
while d <= X:
    d += L[ans]
    ans += 1
print(ans)
Problem p03006 (python)

Fixed submission:
from collections import Counter
N=int(input())
balls=[tuple(map(int, input().split())) for _ in range(N)]

#2ボールの相対座標をぜんぶ調べる
R=[(x[0]-y[0],x[1]-y[1]) for x in balls for y in balls]
C=Counter(R).most_common()

#いちばん多い相対座標を(p,q)とする
#C[0]は(0,0)なので除外
if len(C)<=1:
    print(N)
else:
    print(N-(C[1][1]))

Buggy submission (verdict: Runtime Error):
from collections import Counter
N=int(input())
balls=[tuple(map(int, input().split())) for _ in range(N)]

#2ボールの相対座標をぜんぶ調べる
R=[(x[0]-y[0],x[1]-y[1]) for x in balls for y in balls]
C=Counter(R).most_common(2)

#いちばん多い相対座標を(p,q)とする
#C[0]は(0,0)なので除外
print(N-(C[1][1]))
Problem p03032 (python)

Fixed submission:
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(min(N,K)+1):
    for r in range(max(1,min(N,K)+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N,K=map(int, input().split())
V=list(map(int, input().split()))

ans=-10**9
for l in range(K+1):
    for r in range(max(1,K+1-l)):
        for d in range(max(1,K+1-l-r)):
            h=V[:l]
            heapq.heapify(h)
            for i in range(r): heapq.heappush(h, V[-1-i])
            for i in range(min(d,len(h))): heapq.heappop(h)
            ans=max(ans,sum(h))
print(ans)
Problem p03037 (python)

Fixed submission:
N, M = map(int, input().split())
l, r = 1, N
for _ in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
print(max(0, r-l+1))

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
l, r = 1, N
for _ in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
print((max(0, r-l+1))
Problem p03043 (python)

Fixed submission:
N,K=map(int, input().split())

t = 0
import math
for x in range(1, min(N,K-1)+1):
    t += (1-pow(0.5, math.ceil(math.log2(K/x))))

print(1 - t / N)

Buggy submission (verdict: Runtime Error):
N,K=map(int, input().split())

t = 0
import math
for x in range(1, min(N,K-1)+1):
    t += (1-pow(0.5, math.ceil(math.log2(K/x))))

print(1 - t / N)
Problem p03216 (python)

Fixed submission:
N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

for k in K:
    ans=0
    d=m=dm=0
    for i in range(min(k-1,N)):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
    for i in range(k-1,N):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
        c=S[i-(k-1)]
        if c==D:
            d-=1
            dm-=m
        elif c==M:
            m-=1
    print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
N=int(input())
S=list(input())
Q=int(input())
K=map(int,input().split())

for k in K:
    ans=0
    d=m=dm=0
    for c in S:
        if c=='D':
            d+=1
        elif c=='M':
            m+=1
            dm+=d
        elif c=='C':
            ans+=dm
        if i>=k-1:
            c=S[i-(k-1)]
            if c=='D':
                d-=1
                dm-=m
            elif c=='M':
                m-=1
    print(ans)
Problem p03287 (python)

Fixed submission:
import sys
from collections import Counter
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    AC = accumulate([0] + A, func=lambda x,y:(x+y)%M)
    ACC = Counter(AC)

    ans = 0
    for c in ACC.values():
        ans += c * (c-1) // 2
    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import Counter
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    AC = accumulate([0] + A, func=lambda x,y:(x+y)%M)
    ACC = Counter(AC)

    ans = 0
    for c in ACC.values():
        ans += c * (c-1) // 2
    print(ans)

if __name__ == '__main__':
    main()
Problem p03343 (python)

Fixed submission:
N,K,Q=map(int, input().split())
*A,=map(int, input().split())

import heapq
ans = 10**10
A.append(-1)
for y in A:
    if y==-1: break
    p,q=[],[]
    for a in A:
        if a >= y:
            heapq.heappush(p, a)
        else:
            for i in range(max(0,len(p)-(K-1))):
                heapq.heappush(q, heapq.heappop(p))
            p=[]
    if len(q) < Q: continue
    x = -1
    for i in range(Q):
        x = heapq.heappop(q)
    ans = min(ans, x-y)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N,K,Q=map(int, input().split())
    *A,=map(int, input().split())

    ans=10**10
    from heapq import heappop, heappush
    A.append(-1)
    for y in A:
        if y==-1: break
        c=[]
        t=[]
        for a in A:
            if a >= y:
                heappush(t, a)
            else:
                for _ in range(len(t)-(K-1)):
                    heappush(c, heappop(t))
                t.clear()
        if len(c) < Q: continue
        x=[heappop(c) for _ in range(Q)][-1]
        ans = min(ans, x-y)
    print(ans)

if __name__ == '__main__':
    main()
Problem p03472 (python)

Fixed submission:
N,H=map(int,input().split())
iAB=[]
a_max=(0,0,0)
for i in range(N):
    a,b=map(int,input().split())
    iAB.append((i,a,b))
    if a_max[1]<a or (a_max[1]==a and a_max[2]>b):
        a_max=(i,a,b)

#最大ダメージの刀以外を振る意味はない
#振った場合の最大ダメージを超えるダメージを投げて出せる刀はどんどん投げる
#最大ダメージの刀を投げて1撃で倒せる状態なら投げる

#投げダメージの降順でソート
iAB.sort(key=lambda x:x[2], reverse=True)

ans=0 #攻撃回数
throw_idx=0 if a_max[0]!=iAB[0][0] else 1 #投げチェックindex

#倒すまでループ
#print(a_max,throw_idx)###########
while H>0:
    if a_max[2]>=H:
        #最大ダメージの刀を投げて1撃で倒せる状態なら投げて終わり
        #print("{0}を最後に投げてHPは{1}になった".format(a_max,H-a_max[2]))
        ans+=1
        break
    if throw_idx<N and iAB[throw_idx][2]>a_max[1]:
        #最大じゃない刀を投げる
        H-=iAB[throw_idx][2]
        #print("{0}を投げてHPは{1}になった".format(iAB[throw_idx],H))
        throw_idx+=1
        throw_idx+=1 if throw_idx<N and iAB[throw_idx][0]==a_max[0] else 0
        ans+=1
        continue
    #もう投げられるものがない
    #振りまくる(投げ分のHPは残す)
    furi=(H-a_max[2])//a_max[1] +(1 if (H-a_max[2])%a_max[1] else 0)
    #print("{0}を{1}回振ってHPは{2}になった".format(a_max,furi,furi*a_max[1]))
    ans+=furi
    H-=furi*a_max[1]
    if a_max[1]>=H:
        #1回振って倒せるなら振って終わり
        #print("{0}を最後に1回振ってHPは{1}になった".format(a_max,H-a_max[1]))
        ans+=1
        break

print(ans)

Buggy submission (verdict: Runtime Error):
N,H=map(int,input().split())
iAB=[]
a_max=(0,0,0)
for i in range(N):
    a,b=map(int,input().split())
    iAB.append((i,a,b))
    if a_max[1]<a or (a_max[1]==a and a_max[2]>b):
        a_max=(i,a,b)

#最大ダメージの刀以外を振る意味はない
#振った場合の最大ダメージを超えるダメージを投げて出せる刀はどんどん投げる
#最大ダメージの刀を投げて1撃で倒せる状態なら投げる

#投げダメージの降順でソート
iAB.sort(key=lambda x:x[2], reverse=True)

ans=0 #攻撃回数
throw_idx=0 if a_max[0]!=iAB[0][0] else 1 #投げチェックindex

#倒すまでループ
#print(a_max,throw_idx)###########
while H>0:
    if a_max[2]>=H:
        #最大ダメージの刀を投げて1撃で倒せる状態なら投げて終わり
        #print("{0}を最後に投げてHPは{1}になった".format(a_max,H-a_max[2]))
        ans+=1
        break
    if throw_idx<N and iAB[throw_idx][2]>a_max[1]:
        #最大じゃない刀を投げる
        H-=iAB[throw_idx][2]
        #print("{0}を投げてHPは{1}になった".format(iAB[throw_idx],H))
        throw_idx+=1
        throw_idx+=1 if iAB[throw_idx][0]==a_max[0] else 0
        ans+=1
        continue
    #もう投げられるものがない
    #振りまくる(投げ分のHPは残す)
    furi=(H-a_max[2])//a_max[1] +(1 if (H-a_max[2])%a_max[1] else 0)
    #print("{0}を{1}回振ってHPは{2}になった".format(a_max,furi,furi*a_max[1]))
    ans+=furi
    H-=furi*a_max[1]
    if a_max[1]>=H:
        #1回振って倒せるなら振って終わり
        #print("{0}を最後に1回振ってHPは{1}になった".format(a_max,H-a_max[1]))
        ans+=1
        break

print(ans)
Problem p03488 (python)

Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if pre[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)

Buggy submission (verdict: Runtime Error):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if dp[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)
Problem p03607 (python)

Fixed submission:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    A=[int(input()) for _ in range(N)]
    from collections import Counter
    C=Counter(A)
    ans=0
    for v in C.values():
        if v&1: ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
import io, os
def main():
    input = sys.stdin.readline
    inputb = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    N=int(input())
    A=[int(input()) for _ in range(N)]
    from collections import Counter
    C=Counter(A)
    ans=0
    for v in C.values():
        if v&1: ans+=1
    print(ans)


if __name__ == '__main__':
    main()
Problem p03608 (python)

Fixed submission:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]-1][rp[i+1]-1]
    ans=min(ans,t)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M,R=map(int, input().split())
r=map(lambda x:int(x)-1, input().split())
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)
Problem p03612 (python)

Fixed submission:
N=int(input())
P=[1]+list(map(int,input().split()))

ans=0
for i in range(1,N+1):
    if P[i]==i:
        if (i<N and i+1==P[i+1]) or i==1:
            P[i+1],P[i]=P[i],P[i+1]
            ans+=1
        else:
            P[i-1],P[i]=P[i],P[i-1]
            ans+=1
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
P=[1]+list(map(int,input().split()))

ans=0
for i in range(1,N+1):
    if P[i]==i:
        if i+1==P[i+1] or i==1:
            P[i+1],P[i]=P[i],P[i+1]
            ans+=1
        else:
            P[i-1],P[i]=P[i],P[i-1]
            ans+=1
print(ans)
Problem p03659 (python)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
a = sum(A) - A[0]
s = A[0]
ans = abs(s - a)
for i in range(1,N-1):
    a -= A[i]
    s += A[i]
    ans = min(ans, abs(s - a))
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
from bisect import bisect_left
from itertools import accumulate
a = map(int, input().split())
A = list(accumulate(a))
m = A[-1]//2
i = bisect_left(A, m)
ans1 = abs(A[-1] - A[i] - A[i])
ans2 = abs(A[-1] - A[i-1] - A[i-1]) if i >= 1 else ans1
print(min(ans1,ans2))
Problem p04026 (python)

Fixed submission:
s=input()
for i in range(len(s)):
    if i>=1:
        if s[i]==s[i-1]:
            print(i, i+1)
            exit()
    if i>=2:
        if s[i]==s[i-2]:
            print(i-1, i+1)
            exit()
print(-1, -1)

Buggy submission (verdict: Runtime Error):
s=input()
for i in range(len(s)):
    if i>=1:
        if s[i]==s[i-1]:
            print(i-1 + ' ' + i)
            exit()
    if i>=2:
        if s[i]==s[i-2]:
            print(i-2 + ' ' + i)
            exit()
print(-1 -1)

Buggy submission (verdict: Runtime Error):
s=input()
'''
- aa
- aba
'''
for i in range(len(s)):
    if i>=1:
        if s[i]==s[i-1]:
            print(i-1 + ' ' + i)
            exit()
    if i>=2:
        if s[i]==s[i-2]:
            print(i-2 + ' ' + i)
            exit()
print(-1 -1)
Problem p02579 (python)

Fixed submission:
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= py + dy < w and 0 <= px + dx < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0<=warpx<w and 0<=warpy<h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)
Problem p02684 (python)

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
x = 1
path.append(x)
for i in range(n):
    x = a[x-1]
    path.append(x)
#print(path)
count = [0]*n
roop_st = 0
roop_len = 0
for town in path:
    count[town-1] += 1
    if count[town-1] == 2:
        roop_st = town
        break
roop_st_idx = path.index(roop_st)
roop_fin_idx = path.index(roop_st, roop_st_idx+1)
#print(roop_st_idx, roop_fin_idx)
if k >= roop_st_idx:
    k_mod = (k - roop_st_idx) % (roop_fin_idx - roop_st_idx)
    print(path[roop_st_idx + k_mod])
else:
    print(path[k])

Buggy submission (verdict: Runtime Error):
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
path.append(1)
x = a[0]
path.append(x)
for i in range(n-2):
    x = a[x-1]
    path.append(x)
#print(path)
c = Counter(path)
roop1 = 0
for key, v in c.items():
    if v == 2:
        roop1 = key
if roop1 == 0:
    roop1 = 1
roopidx = path.index(roop1)
roopidx2 = path.index(roop1, roopidx+1)
#print(roopidx,roopidx2)
k_mod = (k-roopidx) % (roopidx2-roopidx)
print(path[roopidx+k_mod])

Buggy submission (verdict: Runtime Error):
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
path.append(1)
x = a[0]
path.append(x)
for i in range(n-2):
    x = a[x-1]
    path.append(x)
print(path)
c = Counter(path)
roop1 = 0
for k, v in c.items():
    if v == 2:
        roop1 = k
if roop1 == 0:
    roop1 = 1
roopidx = path.index(roop1)
roopidx2 = path.index(roop1, roopidx+1)
print(roopidx,roopidx2)
k_mod = (k-roopidx) % (roopidx2-roopidx)
print(path[k_mod+roopidx-1])