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

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


par  =[]
N = int(input())

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)

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

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)

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

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)
Problem p02615 (python)

Fixed submission:
num = int(input())
a_i = list(map(int, input().split()))
list.sort(a_i, reverse=True)
if num <= 3:
    print(sum(a_i[:num - 1]))
else:
    ans = sum(a_i[:2])
    for x in range(3, num):
        if x == 3: ans += a_i[1]
        else: ans += a_i[x // 2]
    print(ans)

Buggy submission (verdict: Runtime Error):
num = int(input())
a_i = list(map(int, input().split()))
list.sort(a_i, reverse=True)
if num <= 3:
    print(sum(a_i[:num - 1]))
else:
    ans = sum(a_i[:2])
    for x in range(3, num):
        if x == 3: ans += a_i[1]
        else: ans += a_i[x // 2]
print(ans)
Problem p02664 (python)

Fixed submission:
str = input()
length = len(str)
ans = [""] * length
for x in range(length):
    if str[length - (x + 1)] == "P":ans[length - (x + 1)] += "P"
    elif str[length - (x + 1)] == "D":ans[length - (x + 1)] += "D"
    elif str[length - (x + 1)] == "?":
        if x == 0 or x == length - 1: ans[length - (x + 1)] = "D"
        elif ans[length - x] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "D": ans[length - (x + 1)] = "P"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "?": ans[length - (x + 1)] = "P"
print(''.join(ans))

Buggy submission (verdict: Runtime Error):
str = input()
length = len(str)
ans = [""] * length
for x in range(length):
    if str[length - (x + 1)] == "P":ans[length - (x + 1)] += "P"
    elif str[length - (x + 1)] == "D":ans[length - (x + 1)] += "D"
    elif str[length - (x + 1)] == "?":
        if x == 0 or x == length: ans[length - (x + 1)] = "D"
        elif ans[length - x] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and ans[length - (x - 1)] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and ans[length - (x - 1)] == "D": ans[length - (x + 1)] = "P"
print(''.join(ans))
Problem p02708 (python)

Fixed submission:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 1):
    premin += list[x]
    premax += list[n - x]
    if x < k - 1: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    premin = sum(list[x])
    premax = sum(list[n + 1 - x])
    if x < k: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    if x < k: continue
    if k < x: ans += pre
    premin = sum(list[0 : x])
    premax = sum(list[n + 1 - x : n + 1])
    ans += (premax - premin + 1) % mod
print(ans)
Problem p02713 (python)

Fixed submission:
import math

num = int(input())
ans = 0
for a in range(num):
    for b in range(num):
        temp = math.gcd(a + 1, b + 1)
        for c in range(num):
            ans += math.gcd(temp, c + 1)
print(ans)

Buggy submission (verdict: Runtime Error):
import math

num = int(input())
ans = 0
for a in num:
    for b in num:
        for c in num:
            ans += math.gcd(a, b, c)
print(ans)
Problem p02717 (python)

Fixed submission:
x, y, z = map(str, input().split())
print(z + " " + x + " " + y)

Buggy submission (verdict: Runtime Error):
x, y, z = map(int, input().split())
print(z + " " + x + " " + y)
Problem p02743 (python)

Fixed submission:
a, b, c = map(int, input().split())
val = a * b
if c - a - b > 0 and 4 * a * b < (c - a - b) ** 2: print('Yes')
else: print('No')

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
if h == 1 or w == 1: print(1)
else: print((h * w + 1) // 2)
Problem p02780 (python)

Fixed submission:
n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
sum = 0
for x in range(n):
    if x <= k - 1: 
        sum += p_i[x]
        if x == k - 1: answer = sum
    else:
        sum += p_i[x] - p_i[x - k]
        answer = max(answer, sum)
print((answer + k) / 2)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
p_i = input().split()
answer = 0
for x in range(n):
    if x <= k - 1:
        sum = 0
        for y in range(k):
            sum += int(p_i[x + y])
        answer = max(answer, sum)
print((answer + k) / 2)
Problem p03125 (python)

Fixed submission:
a, b = map(int, input().split())
if b % a == 0: print(a + b)
else: print(b - a)

Buggy submission (verdict: Runtime Error):
a, b = map(int, input().split())
if b % a　== 0: print(a + b)
else: print(b - a)
Problem p03964 (python)

Fixed submission:
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    m = -min(-pret//t,-prea//a)
    pret = m * t
    prea = m * a
print(pret + prea)

Buggy submission (verdict: Runtime Error):
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    else:
        m = max(math.ceil(pret / t), math.ceil(prea / a))
        pret = m * t
        prea = m * a
print(pret + prea)
Problem p04045 (python)

Fixed submission:
n, k = map(int, input().split())
d_k = set(map(int, input().split()))
ans = n
while ans <= n * 10:
    isOK = True
    for x in range(len(str(ans))):
        if int(str(ans)[x]) in d_k: 
            isOK = False
            break
    if isOK == True: break
    ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
n, k = map(int, input().split())
d_i = set(map(int, input().split()))
full = set(range(10))
useableList = full - d_i
useable_Top = full - d_i - set([0])
answer = []
isTop = True
for x in str(n):
    if int(x) in useableList: answer.append(x)
    elif isTop: answer.append(min(useable_Top - set(range(int(x) + 1))))
    else: answer.append(min(useableList))
    if isTop: isTop = False;
ans = ''
for x in range(len(answer)):
    ans += str(answer[x])
print(ans)
Problem p02617 (python)

Fixed submission:
def main():
    N = int(input())
    h = 0
    for _ in range(N - 1):
        u, v = map(int, input().split())
        if u > v:
            u, v = v, u
        h += u * (N + 1 - v)

    return N * (N + 1) * (N + 2) // 6 - h

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    E = [0] * N
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        if u > v:
            u, v = v, u
        E[v] += 1
    t = 0
    U = [0] * N
    for i in range(N):
        t += E[i]
        U[i] = t

    t = n * (n + 1) * (n + 2 ) // 6
    for i in range(N):
        t += U[i] * i - U[i] * (N - i)
    return t

print(main())
Problem p02697 (python)

Fixed submission:
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        s = set()
        t = 0
        for i in range(M):
            a, b = i + 1, N - i - t
            if (b - a) in s or (a + N - b) in s or b - a == a + N - b:
                t += 1
                b = N - i - t
            print(a, b)
            s.add(b - a)
            s.add(N + a - b)

main()

Buggy submission (verdict: Runtime Error):
def main():
    N, M = list(map(int, input().split()))
    if N % 2 == 1:
        for i in range(M):
            print(i + 1, N - i - 1)
            
    else:
        A = [False] * N
        t = 0
        for i in range(M):
            while True:
                while A[t]:
                    t += 1
                A[t] = True
                if A[(t + i + 1)% N]:
                    A[t] = False
                    t += 1
                    continue
                break
            A[(t + i + 1) % N] = True
            print(t + 1, t + i + 2)

main()
Problem p02715 (python)

Fixed submission:
def ff(n):
    i = 1
    r = set()
    while i * i <= n:
        if n % i == 0:
            r.add(i)
            if i != n // i:
                r.add(n // i)
        i += 1
    return sorted(r)

def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    T = [[] for _ in range(K + 1)]
    F = [ff(i) for i in range(K + 1)]
    for i, f in enumerate(F[1:], 1):
        for j in f:
            T[j].append(i)
    r = 0
    t = [0] * (K + 1)

    for i in reversed(range(1, K + 1)):
        q = (pow(len(T[i]), N, mod) - t[i]) % mod
        for j in F[i][:-1]:
            t[j] = (t[j] + q) % mod
        r = (r + i * q) % mod

    return r

print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())
Problem p02768 (python)

Fixed submission:
def pow2(n, mod):
    p = 2
    r = 1
    while n:
        if n % 2:
            r = r * p % mod
        p = (p * p) % mod
        n //= 2
    return r

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def nCr(n, r, mod):
    t = 1
    r = min(r, n - r)
    for i in range(n - r + 1, n + 1):
        t = t * i % mod
    return t * g2[r] % mod



def prep(n, mod):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

def main():
    n, a, b = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    prep(2 * (10 ** 5) + 1, mod)
    print((pow2(n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod))% mod)


main()

Buggy submission (verdict: Runtime Error):
def pow2(n, mod):
    p = 2
    r = 1
    while n:
        if n % 2:
            r = r * p % mod
        p = (p * p) % mod
        n //= 2
    return r

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def nCr(n, r, mod):
    t = 1
    r = min(r, n - r)
    for i in range(n - r + 1, n + 1):
        t = t * i % mod
    return t * g2[r] % mod



def prep(n, mod):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

def main():
    n, a, b = list(map(int, input().split()))
    aod = 10 ** 9 + 7
    prep(2 * (10 ** 5), mod)
    print((pow2(n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod))% mod)


main()

Buggy submission (verdict: Runtime Error):
def pow2(n, mod):
    p = 2
    r = 1
    while n:
        if n % 2:
            r = r * p % mod
        p = (p * p) % mod
        n //= 2
    return r

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def nCr(n, r, mod):
    t = 1
    for i in range(n - r + 1, n + 1):
        t = t * i % mod
    return t * g2[r] % mod



def prep(n, mod):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

def main():
    n, a, b = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    prep(2 * (10 ** 5), mod)
    print((pow2(n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod))% mod)


main()

Buggy submission (verdict: Runtime Error):
def pow2(n, mod):
    p = 2
    r = 1
    while n:
        if n % 2:
            r = r * p % mod
        p = (p * p) % mod
        n //= 2
    return r

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

def nCr(n, r, mod):
    t = 1
    for i in range(n - r + 1, n + 1):
        t = t * i % mod
    return t * g2[r] % mod



def prep(n, mod):
    for i in range(2, n):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

def main():
    n, a, b = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    prep(2 * (10 ** 5), mod)
    print((pow2(n, mod) - 1 - nCr(n, a, mod) - nCr(n, b, mod))% mod)


main()
Problem p02803 (python)

Fixed submission:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    g = csgraph_from_dense(m)
    EE = floyd_warshall(g)
    print(int(np.max(EE[~np.isinf(EE)])))


main()

Buggy submission (verdict: Runtime Error):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    EE = shortest_path(csgraph_from_dense(m, null_value=0))
    print(int(np.max(EE[~np.isinf(EE)])))


main()
Problem p02814 (python)

Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort(reverse=True)
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            if l // 2 > M:
                return 0
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Buggy submission (verdict: Runtime Error):
from math import gcd

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

def invalid(a, b):
    if a > b:
        a, b = b, a
    return (b % a == 0 and ((b - a) // 2) % a != 0)

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    A.sort()
    if len(A) == 1:
        l = A[0]
    else:
        if invalid(A[0], A[1]):
            return 0
        l = lcm(A[0], A[1])
        for i in A[2:]:
            if invalid(l, i):
                return 0
            if l % i == 0:
                continue
            l = lcm(l, i)
    return (M + l // 2) // l

print(main())

Buggy submission (verdict: Runtime Error):
from math import gcd

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

def main():
    N, M = map(int, input().split())
    A = list(set(map(int, input().split())))
    if len(A) == 1:
        l = A[0]
    else:
        l = lcm(A[0], A[1])
        for i in A[2:]:
            l = lcm(l, i)
    print((M + l // 2) // l)

main()
Problem p02850 (python)

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

def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    E = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        E[a].add(b)
        E[b].add(a)
    c = [0] * N
    clrs = max(len(i) for i in E)
    BAD = 1 << clrs - 1
    def color(n):
        t = set()
        for i in E[n]:
            t.add(c[i])
        for i in range(1, clrs + 1):
            if i in t:
                continue
            c[n] = i
            for j in E[n]:
                if c[j] == 0:
                    color(j)
            return
        raise
    color(0)
    print(clrs)
    for i in c:
        print(i)

main()