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

Fixed submission:
from numpy.linalg import matrix_power
from numpy import dot

class mint:
    def __init__(self, n):
        self.n = n % mod

    def __add__(self, other):
        return mint(self.n + other.n)

    def __mul__(self, other):
        return mint(self.n * other.n)

    def __repr__(self):
        return str(self.n)


L, A, B, mod = map(int, input().split())

ans = [mint(0), mint(A), mint(B)]

size = 0
for d in range(1, 19):
    x = pow(10, d, mod)
    T = [
        [mint(x), mint(0), mint(0)],
        [mint(1), mint(1), mint(0)],
        [mint(0), mint(1), mint(1)],
    ]

    cnt = min(L - size, max(0, 10 ** d - 1 - A) // B - size + 1)
    if cnt > 0:
        ans = dot(ans, matrix_power(T, cnt))

    size += cnt
    if size >= L:
        break

print(ans[0])

Buggy submission (verdict: Runtime Error):
from numpy.linalg import matrix_power

class mint:
    def __init__(self, n):
        self.n = n % mod

    def __add__(self, other):
        return mint(self.n + other.n)

    def __mul__(self, other):
        return mint(self.n * other.n)

    def __repr__(self):
        return str(self.n)


L, A, B, mod = map(int, input().split())

ans = [mint(0), mint(A), mint(B)]

size = 0
for d in range(1, 19):
    x = pow(10, d, mod)
    T = [
        [mint(x), mint(0), mint(0)],
        [mint(1), mint(1), mint(0)],
        [mint(0), mint(1), mint(1)],
    ]

    cnt = min(L - size, max(0, 10 ** d - 1 - A) // B - size + 1)
    if cnt > 0:
        ans = ans @ matrix_power(T, cnt)

    size += cnt
    if size >= L:
        break

print(ans[0])
Problem p03018 (python)

Fixed submission:
S = input().replace("BC", "D")

ans = a = 0
for s in S:
    if s == "A":
        a += 1
    elif s == "D":
        ans += a
    else:
        a = 0

print(ans)

Buggy submission (verdict: Runtime Error):
N, A, B, C, D = [int(i) for i in input().split()]
S = input()

def solve():
    ac, bd = S[A - 1:C], S[B - 1:D]
    if A < B < D < C:
        bd = S[B - 2:D + 1]
        return ("..." in bd and "##" not in ac)
    else:
        return ("##" not in ac and "##" not in bd)

if solve():
    print("Yes")
else:
    print("No")
Problem p03127 (python)

Fixed submission:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

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

result = 0
for ai in A:
    result = gcd(result, ai)

print(result)

Buggy submission (verdict: Runtime Error):
from functools import reduce
from functools import gcd

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

print(reduce(gcd, A))
Problem p03201 (python)

Fixed submission:
from collections import Counter

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

C = Counter(A)
A.sort(reverse=True)

ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1

    b = 2 ** a.bit_length() - a
    if C[b] > 0:
        C[b] -= 1
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

uint32_t ceil2(uint32_t a)
{
    uint32_t b = 1;
    while (a > b) {
        b <<= 1;
    }
    return b;
}

int main()
{
    int N;
    cin >> N;

    multiset<int> S;
    vector<int> A(N);
    for (auto &&a : A) {
        cin >> a;
        S.insert(a);
    }
    sort(rbegin(A), rend(A));

    int ans = 0;
    for (auto a : A) {
        if (S.find(a) != S.end()) {
            S.erase(a);
            int p = ceil2(a) - a;
            if (S.find(p) != S.end()) {
                S.erase(p);
                ans += 1;
            }
        }
    }

    cout << ans << '\n';
}

Buggy submission (verdict: Runtime Error):
N, *A = map(int, open(0).read().split())

S = set(A)

A.sort(reverse=True)

ans = 0
for a in A:
    b = 2 ** a.bit_length() - a
    if a != b and b in S:
        S.remove(a)
        S.remove(b)
        ans += 1

print(ans)
Problem p03307 (python)

Fixed submission:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
N = int(input())

print(2 * N // gcd(N, 2))

Buggy submission (verdict: Runtime Error):
import math

N = int(input())

print(2 * N // math.gcd(N, 2))
Problem p03326 (python)

Fixed submission:
# https://atcoder.jp/contests/abc100/tasks/abc100_d

from itertools import product

N, M, *XYZ = map(int, open(0).read().split())

P = tuple(product((1, -1), repeat=3))

A = [[] for _ in range(8)]
for x, y, z in zip(*[iter(XYZ)] * 3):
    for i, (a, b, c) in enumerate(P):
        A[i].append(a * x + b * y + c * z)

cand = []
for i in range(8):
    A[i].sort(reverse=True)
    cand.append(sum(A[i][:M]))

print(max(cand))

Buggy submission (verdict: Runtime Error):
N, M, *XYZ = map(int, open(0).read().split())

P = tuple(product((1, -1), repeat=3))

A = [[] for _ in range(8)]
for x, y, z in zip(*[iter(XYZ)] * 3):
    A[0].append(sum((x, y, z)))
    A[1].append(sum((x, y, -z)))
    A[2].append(sum((x, -y, z)))
    A[3].append(sum((x, -y, -z)))
    A[4].append(sum((-x, y, z)))
    A[5].append(sum((-x, y, -z)))
    A[6].append(sum((-x, -y, z)))
    A[7].append(sum((-x, -y, -z)))

cand = []
for i in range(8):
    A[i].sort(reverse=True)
    cand.append(sum(A[i][:M]))

print(max(cand))
Problem p03634 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])

Buggy submission (verdict: Runtime Error):
N = int(input())

E = [[] for _ in range(N + 1)]
for a, b, c in [[int(i) for i in input().split()] for _ in range(N - 1)]:
    E[a].append((b, c))
    E[b].append((a, c))


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

for x, y in [[int(i) for i in input().split()] for _ in range(Q)]:
    print(dist[x] + dist[y])
Problem p03776 (python)

Fixed submission:
def combinations(N):
    comb = [[0] * (N + 1) for _ in range(N + 1)]
    comb[0][0] = 1
    for i in range(1, N + 1):
        for j in range(i + 1):
            comb[i][j] += comb[i - 1][j]
            if j > 0:
                comb[i][j] += comb[i - 1][j - 1]
    return comb


nCk = combinations(60)

N, A, B, *V = map(int, open(0).read().split())

V.sort(reverse=True)

num = V.count(V[A - 1])

ans = 0
if V[0] == V[A - 1]:
    for i in range(A, B + 1):
        ans += nCk[num][i]
else:
    a = V[:A].count(V[A - 1])
    ans = nCk[num][a]

ave = sum(V[:A]) / A

print("{:.9f}".format(ave))
print(ans)

Buggy submission (verdict: Runtime Error):
def divisors(N):
    U = int(N ** 0.5)
    L = [i for i in range(1, U) if N % i == 0]
    C = [U] if M % U == 0 else []
    R = [N // r for r in reversed(L)]
    return L + C + R

N, M = map(int, input().split())
print(max(d for d in divisors(M) if d * N <= M))
Problem p03822 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

N, *A = map(int, open(0))

E = [[] for _ in [0] + A]
for i, v in enumerate(A, 1):
    E[v - 1] += i,

def dfs(v):
    D = sorted(map(dfs, E[v]))
    l = len(D)
    return max([0] + [l - i + d for i, d in enumerate(D)])

print(dfs(0))

Buggy submission (verdict: Runtime Error):
N, *A = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, v in enumerate(A, 1):
    E[v - 1].append(i)

def dfs(v):
    D = sorted(dfs(u) for u in E[v])
    return max([0] + [len(D) - i + d for i, d in enumerate(D)])

print(dfs(0))
Problem p02550 (python)

Fixed submission:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
U = [0] * (M + 10)
U[X] = 1
S = [0] * (M + 10)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N <= l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)

Buggy submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
U = [0] * (M + 10)
U[X] = 1
S = [0] * (M + 10)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N < l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)

Buggy submission (verdict: Runtime Error):
N, X, M = map(int, input().split())
U = [0] * (M)
U[X] = 1
S = [0] * (M)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N < l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)
Problem p02598 (python)

Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from math import ceil
def main(N, K, A):
    A.sort(reverse=True)

    def f(x):
        res = 0
        for a in A:
            if a > x:
                res += a // x
            else:
                break
        return res

    lo = 0
    hi = 10**9
    for _ in range(100):
        m = (lo + hi) / 2
        if f(m) > K: lo = m
        else: hi = m
    print(ceil(lo))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    main(N, K, A)

Buggy submission (verdict: Runtime Error):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, K, A):
    lo = -1
    hi = 10**9
    while hi - lo > 1:
        m = (lo + hi) // 2
        if sum((a + m - 1) // m - 1 for a in A) <= K: hi = m
        else: lo = m
    print(hi)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    * A, = map(int, input().split())
    main(N, K, A)
Problem p02623 (python)

Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import accumulate
import sys
def main(N, M, K, A, B):
    *AA, = accumulate(A, initial=0)
    *BB, = accumulate(B, initial=0)

    def f(c):
        res = 10 ** 18
        for a in range(max(0, c - M), min(c, N) + 1):
            res = min(res, AA[a] + BB[c - a])
        return res

    l = 0
    r = N + M + 1
    while r - l > 1:
        m = (l + r) // 2
        if f(m) > K:
            r = m
        else:
            l = m
    print(l)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    main(N, M, K, A, B)

Buggy submission (verdict: Runtime Error):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import accumulate
import sys
def main(N, M, K, A, B):
    *AA, = accumulate(A, initial=0)
    *BB, = accumulate(B, initial=0)

    def f(c):
        res = 10 ** 18
        for a in range(max(0, c - M), min(c, N) + 1):
            res = min(res, AA[a] + BB[c - a])
        return res

    l = 0
    r = N + M + 1
    while r - l > 1:
        m = (l + r) // 2
        if f(m) > K:
            r = m
        else:
            l = m
    print(l)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    main(N, M, K, A, B)
Problem p02762 (python)

Fixed submission:
N,M,K=map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(K)]

def root(x,P):
    l = []
    n = x
    p = P[n]
    while p >= 0:
        l.append(n)
        n = p
        p = P[p]
    for a in l: P[a] = n
    return n

def same(a, b, P): return root(a,P) == root(b,P)

def count(x,P): return -P[root(x,P)]

def unite(a, b, P):
    if count(a,P) < count(b,P): a, b = b, a
    ar = root(a,P)
    br = root(b,P)
    if ar == br: return
    P[ar] += P[br]
    P[br] = ar

Fu = [-1] * N
F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for a,b in AB:
    a, b = a-1, b-1
    unite(a,b,Fu)
    F[a].add(b)
    F[b].add(a)
for c,d in CD:
    c, d = c-1, d-1
    B[c].add(d)
    B[d].add(c)

for i in range(N):
    block = 0
    for b in B[i]:
        if same(i,b,Fu): block += 1
    print(count(i,Fu) - len(F[i]) - block - 1, end=' ')

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        friends_chain.unite(a, b)
        friend_or_block[a] += 1
        friend_or_block[b] += 1

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

    class UnionFindTree:
        def __init__(self, n):
            self.parent = [-1] * n

        def root(self, x):
            p, s = self.parent[x], list()
            while p >= 0:
                s.append(x)
                x, p = p, self.parent[p]
            for c in s: self.parent[c] = x
            return x

        def same(self, x, y): return self.root(x) == self.root(y)

        def count(self, x): return -self.parent[self.root(x)]

        def unite(self, x, y):
            xr, yr = self.root(x), self.root(y)
            if xr == yr: return
            if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
            self.parent[xr] += self.parent[yr]
            self.parent[yr] = xr

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

Fixed submission:
N=int(input())
K=int(input())

sN=str(N)
keta=len(sN)

#dp[i][j][t]=Nと同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(1,keta+1):
    for j in range(K+1):
        if sN[i-1]=='0':
            dp[i][j][1] = dp[i-1][j][1]
        elif j>0:
            dp[i][j][1] = dp[i-1][j-1][1]
        dp[i][j][0] = dp[i-1][j][0]
        if sN[i-1]!='0':
            dp[i][j][0] += dp[i-1][j][1]
        if j>0:
            dp[i][j][0] += dp[i-1][j-1][1]*(max(0,int(sN[i-1])-1))
            dp[i][j][0] += dp[i-1][j-1][0]*9

print(dp[keta][K][0]+dp[keta][K][1])

Buggy submission (verdict: Runtime Error):
N = int(input())
K = int(input())

#桁DP
string = str(N)
digits = len(string)

#dp[i][j][k]=と同じ桁数の整数で上からi桁目までで0でない数字がj個あるものの個数
#k=0: i桁目まで見てN未満が確定, k=1: 未確定
dp = [[[0]*2 for _ in range(K+1)] for __ in range(digits+1)]
#初期状態
dp1[0][0][1] = 1

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nk = 1 if k == 1 and nd == d else 0
                if k == 1 and nd > d: break

                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue

                dp[ni][nj][nk] += dp[i][j][k]

print(dp[digits][K][0] + dp[digits][K][1])
Problem p02792 (python)

Fixed submission:
N=int(input())

def cnt(i,j):
    ret=0
    si=str(i)
    for n in range(1,N+1):
        if n%10!=j:
            continue
        if str(n)[0]!=si:
            continue
        ret+=1
    return ret

ans=0
for i in range(10):
    for j in range(10):
        ans+=cnt(i,j)*cnt(j,i)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    str_N = str(N)
    head_N, tail_N = int(str_N[0]), int(str_N[-1])
    digits = len(str_N)
    m = int(str_N[1:-1])
        
    def f(x):
        s = str(x)
        head, tail = int(s[0]), int(s[-1])
        res = 0
        if head == tail: res += 1 #1桁
        if digits >= 2: #2桁
            if digits == 2:
                if tail <= head_N: res += 1
            else: res += 1
        for d in range(3, digits+1): #3桁以上
            k = d - 2
            if d == digits: #Nと同じ桁数
                if tail < head_N:
                    res += 10**k
                elif tail == head_N:
                    res += m
            else: res += 10**k

        return res

    ans = 0
    for n in range(1,N+1):
        if n % 10 == 0: continue
        ans += f(n)
    print(ans)

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

Fixed submission:
from collections import deque
from collections import Counter
N=int(input())
E=[set() for _ in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    E[a].add((b,i))
    E[b].add((a,i))
M=int(input())
P=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

pc=[set() for _ in range(M)] #各制約で使用する辺の集合

def bfs(S,G,p):
    q=deque([S])
    parent=[(-1,-1)]*N
    while q:
        n=q.popleft()
        for to,i in E[n]:
            if parent[to][0]!=-1:
                continue
            parent[to]=(n,i)
            if to==G:
                break
            q.append(to)
    n=G
    while n!=S:
        n,i=parent[n]
        pc[p].add(i)

for i,p in enumerate(P):
    bfs(p[0],p[1],i)

ans=0
for i in range(1<<M):
    whiteset=set()
    sign=1
    for j in range(M):
        if i>>j&1:
            whiteset|=pc[j]
            sign*=-1
    ans+=sign*(1<<(N-1-len(whiteset)))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

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

Fixed submission:
N,u,v = map(int,input().split())
u -= 1
v -= 1
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)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
parent = [-1]*N
def dfs(root,end):
    global r
    stack = []
    stack.append(root)
    parent[root] = root
    while len(stack)>0:
        p = stack.pop()
        if p==end:
            break
        for e in E[p]:
            if parent[e]==-1:
                parent[e] = p
                stack.append(e)
    p=end
    while p!=root:
        r.append(p)
        p = parent[p]
    r.append(root)

dfs(v,u)
ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
depth = [-1]*N
def dfs2(root,end,d):
    global dmax
    stack = []
    stack.append(root)
    depth[root] = d
    depth[end] = 0
    while len(stack)>0:
        p = stack.pop()
        for e in E[p]:
            if depth[e]==-1:
                depth[e] = depth[p]+1
                dmax = max(dmax,depth[e])
                stack.append(e)

dfs2(u,v,0)
ans += dmax - 1

print(ans)

Buggy submission (verdict: Runtime Error):
import queue
N,u,v = map(int,input().split())
u -= 1
v -= 1
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)

ans = 0
if u==v:
    print(0)
    exit()

#u〜vの最短経路を求める
r = []
used = [False]*N
def dfs(i,end):
    global r
    used[i] = True
    if i==end:
        r.append(i)
        return True
    for e in E[i]:
        if not used[e]:
            if dfs(e,end):
                r.append(i)
                return True
    return False
dfs(v,u)

ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]

#uから最も遠い頂点までの距離を求める
dmax = 0
used = [False]*N
def dfs2(i,end,d):
    global dmax
    used[i] = True
    if i==end:
        return
    dmax = max(dmax,d)
    for e in E[i]:
        if not used[e]:
            dfs2(e,end,d+1)
dfs2(u,v,0)
ans += dmax - 1

print(ans)
Problem p02912 (python)

Fixed submission:
import heapq
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [(-x, x) for x in A]
heapq.heapify(A)
for i in range(M):
    P = heapq.heappop(A)
    p = P[1] // 2
    heapq.heappush(A, (-p, p))
s = 0
for i in range(N):
    s += A[i][1]
print(s)

Buggy submission (verdict: Runtime Error):
from collections import deque
import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
A = deque(A)
for i in range(M):
    A[N-1] //= 2
    if N >=2 and A[N-1] > A[N-2]:
        continue
    p = A.pop()
    index = bisect.bisect_left(A, p)
    A.insert(index, p)
print(sum(A))
Problem p02915 (python)

Fixed submission:
N = int(input())
print(N**3)

Buggy submission (verdict: Runtime Error):
N=input()
print(N*N*N)
Problem p03018 (python)

Fixed submission:
s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)

Buggy submission (verdict: Runtime Error):
s = list(input())

ans = 0
i = 0
if s[0] == 'A' and s[1] == 'B' and s[2] == 'C':
    s[0] = 'B'
    s[1] = 'C'
    s[2] = 'A'
    ans += 1
    i = 3

while i+2 < len(s):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
        ans += 1
        s[i] = 'B'
        s[i+1] = 'C'
        s[i+2] = 'A'
        i -= 1
    else:
        i += 1

print(ans)
Problem p03038 (python)

Fixed submission:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *A,=map(int, input().split())
    BC=[tuple(map(int, input().split())) for _ in range(M)]

    A.sort()
    BC.sort(key=lambda x:x[1], reverse=True)
    ans=0
    i=0
    from bisect import bisect_right
    for b,c in BC:
        j = bisect_right(A, c, i, min(N,i+b))
        ans += c*(j-i)
        i=j
    for j in range(i,N):
        ans+=A[j]
    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *A,=map(int, input().split())
    BC=[tuple(map(int, input().split())) for _ in range(M)]

    A.sort()
    BC.sort(key=lambda x:x[1], reverse=True)
    ans=0
    i=0
    from bisect import bisect_right
    for b,c in BC:
        j = bisect_right(A, c, i, i+b)
        ans += c*(j-i)
        i=j
    for j in range(i,N):
        ans+=A[j]
    print(ans)

if __name__ == '__main__':
    main()