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

Fixed submission:
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0 and K >= N:
        q, K = divmod(K, N)
        K += N
        ans = sumC * (q - 1)
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now):
        acc = C[now]
        ret = acc
        for _ in range(K - 1):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start))

    return mx + ans

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)

    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC >= 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)
        1 / 0

    if K == 0:
        return ans

    def calc(now, K):
        ret = -INF
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start, K))

    return ans + mx

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)
Problem p02609 (python)

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

cnt = X.count('1')
if cnt == 1:
    for x in X[:-1]:
        if x == '0':
            print(1)
        else:
            print(0)
    if X[-1] == '1':
        print(0)
    else:
        print(2)
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

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

cnt = X.count('1')
if cnt == 1:
    print(*([1] + N), sep='\n')
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')

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

cnt = X.count('1')
M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')
Problem p02669 (python)

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

T = int(input())
INF = 10**18

for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    V = set()

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print(search(N))

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

def main(A):
    return 0

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import main

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)

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

def main(A):
    return 0

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import solve

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)

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

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import solve

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

def main(A):
    return 0

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)
Problem p02686 (python)

Fixed submission:
N = int(input())
S = [input() for _ in range(N)]

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less - (r - l), s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = len(ans) - l

if l != r or calc(ans) < 0:
    print('No')
else:
    print('Yes')

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = ans.count(')')

if l == r and calc(ans) == 0:
    assert 0
    print('Yes')
else:
    print('No')

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

def calc(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less, s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = ans.count(')')

if l == r and calc(ans) == 0:
    print('Yes')
else:
    assert 0
    print('No')
Problem p02692 (python)

Fixed submission:
from itertools import combinations

N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

cnt = {'A': A, 'B': B, 'C': C}

def out(T):
    now = {'A': A, 'B': B, 'C': C}

    ans = []
    for i, s in enumerate(S):
        u, v = s[0], s[1]
        if now[u] == now[v] == 0:
            return []
        if now[u] > now[v]:
            ans.append(v)
            now[u] -= 1
            now[v] += 1
            continue
        if now[u] < now[v]:
            ans.append(u)
            now[u] += 1
            now[v] -= 1
            continue
        if i == N - 1:
            ans.append(u)
            continue

        nx = S[i + 1]
        if u in nx:
            ans.append(u)
            now[u] += 1
            now[v] -= 1
            continue
        if v in nx:
            ans.append(v)
            now[v] += 1
            now[u] -= 1
            continue

    return ans

ans = out('')
if len(ans) == 0:
    print('No')
    exit()
print('Yes')
print(*ans, sep='\n')

# for s in combinations(['', '', 'A', 'B', 'C'], r=3):
#     s = ''.join(s)
#     for t in s:
#         if cnt[t] == 0:
#             break
#     else:
#         ans = out(s)
#         if len(ans) == 0:
#             continue
#         print('Yes')
#         print(*ans, sep='\n')
#         exit()

# print('No')

Buggy submission (verdict: Runtime Error):
from itertools import combinations

N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

cnt = {'A': A, 'B': B, 'C': C}

def out(T):
    now = {'A': 0, 'B': 0, 'C': 0}
    for s in T:
        now[s] += 1

    ans = []
    for i, s in enumerate(S):
        if min(now.values()) < 0:
            return False
        if now[s[0]] > now[s[1]]:
            ans.append(s[1])
            now[s[0]] -= 1
            now[s[1]] += 1
            continue
        if now[s[0]] < now[s[1]]:
            ans.append(s[0])
            now[s[0]] += 1
            now[s[1]] -= 1
            continue
        if i == N - 1:
            ans.append(s[0])
            continue
        nx = S[i + 1]
        if nx == s:
            ans.append(s[0])
            now[s[0]] += 1
            now[s[1]] -= 1
            continue
        k = list(set(list(s)) & set(list(nx)))
        k = k[0]
        ans.append(k)
        now[k] += 1
        k = s.replace(k, '')
        now[k] -= 1

    if min(now.values()) < 0:
        return []
    return ans

for s in combinations(['', '', 'A', 'B', 'C'], r=3):
    s = ''.join(s)

    for t in s:
        if cnt[t] == 0:
            break
    else:
        ans = out(s)
        if len(ans) == 0:
            continue
        print('Yes')
        print(*ans, sep='\n')
        exit()

print('No')
Problem p02698 (python)

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

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_left(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')

Buggy submission (verdict: Runtime Error):
from bisect import bisect_right

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_right(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')
Problem p02722 (python)

Fixed submission:
N = int(input())

def isOk(k):
    n = N
    while n % k == 0:
        n //= k
    return n % k == 1

if N <= 10**6:
    ans = 0
    for i in range(2, N + 1):
        if isOk(i):
            ans += 1
    print(ans)
    exit()

ans = 0
V = set()
for i in range(2, int(N**0.5) + 10):
    if isOk(i):
        ans += 1
        V.add(i)

# 約数の全列挙
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort(reverse=True)  # ソート
    return divisors

divN = divisors(N - 1)

ans += len([d for d in divN if not d in V])
print(ans)

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

print(gcd(120, 24))
Problem p02749 (python)

Fixed submission:
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N
nums = set(range(1, N + 1))

if len(A) <= N // 3:
    mul = 1
    for i in A:
        ans[i] = 3 * mul
        nums.remove(3 * mul)
        mul += 1
    nums = list(nums)
    for i, n in zip(B, nums):
        ans[i] = n
else:
    mul = 1
    for c, i in enumerate(A):
        if c * 3 + 1 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 1
    for c, i in enumerate(B):
        if c * 3 + 2 > N:
            ans[i] = mul * 3
            mul += 1
        else:
            ans[i] = c * 3 + 2

print(*ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

dist = [10**10] * N
que = deque([(0, 0)])
while que:
    now, d = que.popleft()

    if dist[now] <= d:
        continue
    dist[now] = d

    for to in edges[now]:
        que.append((to, d + 1))

A = [i for i, d in enumerate(dist) if d % 2 == 0]
B = [i for i, d in enumerate(dist) if d % 2 == 1]

if len(A) > len(B):
    A, B = B, A

ans = [-1] * N

if len(A) <= N // 3:
    nums = set(range(1, N + 1))
    now = 3
    for i in A:
        ans[i] = now
        nums.remove(now)
        now += 3
    nums = list(nums)
    for i, n in zip(B):
        ans[i] = n
else:
    now = 0
    nums = set(range(1, N + 1))
    for i in A:
        if now + 1 > N:
            break
        ans[i] = now + 1
        nums.remove(now + 1)
        now += 3
    now = 0
    for i in B:
        if now + 2 > N:
            break
        ans[i] = now + 2
        nums.remove(now + 2)
        now += 3
    now = 3
    for i, a in enumerate(ans):
        if a == -1:
            ans[i] = now
            now += 3

print(*ans)
Problem p02768 (python)

Fixed submission:
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, A, B = map(int, input().split())
MOD = 10**9 + 7

def calc(k):
    ret = 1
    for i in range(k):
        ret = ret * (N - i) * pow(i + 1, MOD - 2, MOD) % MOD
    return ret

ans = pow(2, N, MOD) - 1 - calc(A) - calc(B)
print(ans % MOD)

Buggy submission (verdict: Runtime Error):
# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, A, B = map(int, input().split())
MOD = 10**9 + 7

def calc(k):
    ret = 1
    for i in range(k):
        ret = ret * (N - i) * pow(i + 1, -1, MOD) % MOD
    return ret

ans = pow(2, N, MOD) - 1 - calc(A) - calc(B)
print(ans % MOD)
Problem p02805 (python)

Fixed submission:
from math import sin

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

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 10**10

for i in range(N):
    for j in range(i + 1, N):
        # 対辺
        xi, yi = XY[i]
        xj, yj = XY[j]
        cx = (xi + xj) / 2
        cy = (yi + yj) / 2
        d = 0
        for x, y in XY:
            d = max(d, dist(x, y, cx, cy))
        ans = min(ans, d)

        for k in range(j + 1, N):
            xi, yi = XY[i]
            xj, yj = XY[j]
            xk, yk = XY[k]
            c = dist(xi, yi, xj, yj)
            a = dist(xj, yj, xk, yk)
            b = dist(xk, yk, xi, yi)

            # 外心
            S = a**2 * (b**2 + c**2 - a**2) + b**2 * (c**2 + a**2 - b**2) + c**2 * (a**2 + b**2 - c**2)
            if S == 0:
                continue
            cx = a**2 * (b**2 + c**2 - a**2) * xi + b**2 * (c**2 + a**2 - b**2) * xj + c**2 * (a**2 + b**2 - c**2) * xk
            cy = a**2 * (b**2 + c**2 - a**2) * yi + b**2 * (c**2 + a**2 - b**2) * yj + c**2 * (a**2 + b**2 - c**2) * yk
            cx /= S
            cy /= S
            d = 0
            for x, y in XY:
                d = max(d, dist(x, y, cx, cy))
            ans = min(ans, d)

print(ans)

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

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

def dist(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

ans = 10**10

for i in range(N):
    for j in range(i + 1, N):
        # 対辺
        xi, yi = XY[i]
        xj, yj = XY[j]
        cx = (xi + xj) / 2
        cy = (yi + yj) / 2
        d = 0
        for x, y in XY:
            d = max(d, dist(x, y, cx, cy))
        ans = min(ans, d)

        for k in range(j + 1, N):
            xi, yi = XY[i]
            xj, yj = XY[j]
            xk, yk = XY[k]
            c = dist(xi, yi, xj, yj)
            a = dist(xj, yj, xk, yk)
            b = dist(xk, yk, xi, yi)

            # 外心
            S = a**2 * (b**2 + c**2 - a**2) + b**2 * (c**2 + a**2 - b**2) + c**2 * (a**2 + b**2 - c**2)
            cx = a**2 * (b**2 + c**2 - a**2) * xi + b**2 * (c**2 + a**2 - b**2) * xj + c**2 * (a**2 + b**2 - c**2) * xk
            cy = a**2 * (b**2 + c**2 - a**2) * yi + b**2 * (c**2 + a**2 - b**2) * yj + c**2 * (a**2 + b**2 - c**2) * yk
            cx /= S
            cy /= S
            d = 0
            for x, y in XY:
                d = max(d, dist(x, y, cx, cy))
            ans = min(ans, d)

print(ans)
Problem p02861 (python)

Fixed submission:
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x, y in XY:
    for u, v in XY:
        ans += length(x, y, u, v)

print(ans / N)

Buggy submission (verdict: Runtime Error):
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x in permutations(range(N)):
    for fr, to in zip(x, x[1:]):
        ans += length(*XY[fr], *XY[to])

for i in range(1, N + 1):
    ans /= i

print(ans)

Buggy submission (verdict: Runtime Error):
from itertools import permutations

N = int(input())

def length(x, y, u, v):
    return ((x - u)**2 + (y - v)**2)**0.5

XY = [tuple(map(int, input().split())) for _ in range(N)]
ans = 0

for x in permutations(range(N)):
    for fr, to in zip(x, x[1:]):
        ans += length(*XY[fr], *XY[to])

for i in range(1, N + 1):
    ans /= i

print(ans)