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

Fixed submission:
import bisect
import sys


sys.setrecursionlimit(10**6)
INF = 10**6


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [- INF] * (2 * N - 1)

    def update(self, i, x):
        n = self.N + i - 1
        self.data[n] = x
        while n > 0:
            n = (n - 1) // 2
            self.data[n] = max(self.data[2 * n + 1], self.data[2 * n + 2])        

    def elem(self, i):
        return self.data[self.N + i - 1]

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return - INF
        if a <= l and r <= b:
            return self.data[k]
        val_left = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
        val_right = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
        return max(val_left, val_right)

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]

    PW_N = 1
    while PW_N < N:
        PW_N *= 2
    next_robot_tree = SegTree(PW_N)
    next_robot_tree.update(N - 1, N)
    for n in range(N - 2, - 1, - 1):
        if X[n] + D[n] <= X[n + 1]:
            next_robot_tree.update(n, n + 1)
        else:
            next_robot = bisect.bisect_left(X, X[n] + D[n])
            next_robot = next_robot_tree.query(n, next_robot)
            next_robot_tree.update(n, next_robot)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        next_robot = next_robot_tree.elem(n)
        cnt[next_robot] += cnt[n]
        cnt[next_robot] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import bisect


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]
    next_robot_list = [-1] * N

    def search_next_robot(r):
        if next_robot_list[r] >= 0:
            return next_robot_list[r]
        if r == N - 1:
            next_robot_list[r] = N
            return N
        if X[r] + D[r] <= X[r + 1]:
            next_robot_list[r] = r + 1
            return r + 1
        next_r_to = bisect.bisect_left(X, X[r] + D[r])
        ret = next_r_to
        for next_r in range(r + 1, next_r_to):
            ret = max(ret, search_next_robot(next_r))
        next_robot_list[r] = ret
        return ret

    for n in range(N):
        search_next_robot(n)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        cnt[next_robot_list[n]] += cnt[n]
        cnt[next_robot_list[n]] %= MOD
    print(cnt[N])


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

Fixed submission:
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    MAX_A = max(list(map(lambda x: x[0], magic)))
    dp = [INF for _ in range(MAX_A + H + 1)]
    dp[0] = 0
    for h in range(1, MAX_A + H + 1):
        for i in range(N):
            a, b = magic[i]
            if h - a < 0:
                continue
            dp[h] = min(dp[h], b + dp[h - a])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    memo = [[INF for _ in range(N)] for _ in range(H + 1)]

    def dfs(h, i=None):
        if h <= 0:
            return 0
        if i is not None and memo[h][i] < INF:
            return memo[h][i]
        ret = INF
        for j in range(N):
            a, b = magic[j]
            ret = min(ret, b + dfs(h - a, j))
        if i is not None:
            memo[h][i] = ret
        return ret

    print(dfs(H))


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

Fixed submission:
from fractions import gcd  # for python 3.5~, use math.gcd


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

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


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm = 1
    for half_a in half_A:
        lcm *= half_a // gcd(lcm, half_a)
        if lcm > M:
            print(0)
            exit(0)
    for half_a in half_A:
        if (lcm // half_a) % 2 == 0:
            print(0)
            exit(0)
    num_multiples = M // lcm
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def gcd(a, b):
    a, b = max([a, b]), min([a, b])
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def gcd_from_list(num_list):
    if len(num_list) == 1:
        return num_list[0]
    else:
        return gcd(num_list[0], gcd_from_list(num_list[1:]))


def lcm_from_list(num_list):
    gcd_of_input = gcd_from_list(num_list)
    num_list = list(set(num_list))
    lcm = num_list[0]
    for i in range(len(num_list) - 1):
        lcm = lcm * num_list[i + 1] // gcd_of_input
    return lcm


def main():
    N, M = list(map(int, input().split(' ')))
    half_A = list(map(lambda x: int(x) // 2, input().split(' ')))
    lcm_A = lcm_from_list(half_A)
    num_multiples = M // lcm_A
    print((num_multiples + 1) // 2)  # count only cases that ratios are odd numbers.


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

Fixed submission:
# 【考察】
# 0-indexedで考える。Aは降順ソートして考える。
# まず、初期状態でTop Pに含まれる問題はすべて出題されうる。
# なので初期でTop q (q > P)の問題が出題されるか否かを考えていく。
# 最終的にTop Pに入れるか否かが問題なので、Top 1 ~ P-1の問題は無視。
# Top qの問題に毎回投票しつつ、Top P ~ q-1の問題になるべく投票しないようにしたい。
# そこで数列 A[P], A[P+1], ..., A[q-1] を考える。
# この中から最大でN-V個の数字を選んで1減らすことをM回繰り返し、
# すべてA[q]以下にすることができればTop qの問題は出題されうる。
# 当然A[P]-A[q] > Mだったら無理（出題されない）。
# 以後A[P]-A[q] <= Mとする。
# この時、(A[P]-A[q]) + (A[P+1]-A[q]) + ... + (A[q-1]-A[q]) <= M * (N-V) であればTop qのは出題可能。
# 整理すると A[P] + A[P+1] + ... + A[q-1] <= M * (N-V) + A[q] * (q-P) となるので、
# Aの累積和のデータを保持しておけば各qにおいてO(1)で出題可否が判定可能。


def main():
    N, M, V, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    P -= 1  # to 0-indexed
    A.sort(reverse=True)  # 降順ソート
    cumsum = [0] * N
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = cumsum[i - 1] + A[i]
    q = P + 1
    while q < N:
        left = cumsum[q - 1]
        if P > 0:
            left -= cumsum[P - 1]
        right = M * (N - V) + A[q] * (q - P)
        if A[P] - A[q] > M or left > right:
            print(q)
            return
        q += 1
    print(q)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# 【考察】
# 0-indexedで考える。Aは降順ソートして考える。
# まず、初期状態でTop Pに含まれる問題はすべて出題されうる。
# なので初期でTop q (q > P)の問題が出題されるか否かを考えていく。
# 最終的にTop Pに入れるか否かが問題なので、Top 1 ~ P-1の問題は無視。
# Top qの問題に毎回投票しつつ、Top P ~ q-1の問題になるべく投票しないようにしたい。
# そこで数列 A[P], A[P+1], ..., A[q-1] を考える。
# この中から最大でN-V個の数字を選んで1減らすことをM回繰り返し、
# すべてA[q]以下にすることができればTop qの問題は出題されうる。
# 当然A[P]-A[q] > Mだったら無理（出題されない）。
# 以後A[P]-A[q] <= Mとする。
# この時、(A[P]-A[q]) + (A[P+1]-A[q]) + ... + (A[q-1]-A[q]) <= M * (N-V) であればTop qのは出題可能。
# 整理すると A[P] + A[P+1] + ... + A[q-1] <= M * (N-V) + A[q] * (q-P) となるので、
# Aの累積和のデータを保持しておけば各qにおいてO(1)で出題可否が判定可能。


def main():
    # N, M, V, P = list(map(int, input().split()))
    # A = list(map(int, input().split()))
    with open('PastAGC/01-08.txt', 'r') as f:
        N, M, V, P = list(map(int, f.readline().split()))
        A = list(map(int, f.readline().split()))
    P -= 1  # to 0-indexed
    A.sort(reverse=True)  # 降順ソート
    cumsum = [0] * N
    cumsum[0] = A[0]
    for i in range(1, N):
        cumsum[i] = cumsum[i - 1] + A[i]
    q = P + 1
    while q < N:
        left = cumsum[q - 1]
        if P > 0:
            left -= cumsum[P - 1]
        right = M * (N - V) + A[q] * (q - P)
        if A[P] - A[q] > M or left > right:
            print(q)
            return
        q += 1
    print(q)


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

Fixed submission:
from collections import defaultdict


def sum_counter(N, adj_nodes, counter_roots, root=0):
    parents = [-1 for _ in range(N)]
    counter = [0 for _ in range(N)]
    frontier = [root]
    counter[root] += counter_roots[root]
    parents[root] = root
    while len(frontier) > 0:
        parent = frontier.pop()
        for child in adj_nodes[parent]:
            if parents[child] >= 0:
                continue
            frontier.append(child)
            parents[child] = parent
            counter[child] += counter[parent] + counter_roots[child]
    return counter


def main():
    N, Q = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    counter_roots = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split(' ')))
        p -= 1
        counter_roots[p] += x
    c = sum_counter(N, adj_nodes, counter_roots)
    print(' '.join(map(str, c)))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def calc_parents(N, adj_nodes, root=0):
    parents = [-1 for _ in range(N)]
    frontier = [root]
    parents[root] = root
    while len(frontier) > 0:
        node = frontier.pop()
        for child in adj_nodes[node]:
            if parents[child] >= 0:
                continue
            frontier.append(child)
            parents[child] = node
    return parents


def sum_counts(N, parents, counter_roots):
    counter = [0 for _ in range(N)]
    for node in range(N):
        current_node = node
        parent_node = parents[current_node]
        s = counter_roots[current_node]
        while current_node != parent_node:
            current_node = parent_node
            parent_node = parents[current_node]
            s += counter_roots[current_node]
        counter[node] += s
    return counter


def main():
    N, Q = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    parents = calc_parents(N, adj_nodes)
    counter_roots = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split(' ')))
        p -= 1
        counter_roots[p] += x
    counter = sum_counts(N, parents, counter_roots)
    print(' '.join(map(str, counter)))


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

Fixed submission:
INF = 10**18


def calc(point_list, t):
    x_min, y_min, x_max, y_max = INF, INF, -INF, -INF
    for point in point_list:
        x, y, d = point
        dx = t if d == 'R' else (-t if d == 'L' else 0)
        dy = t if d == 'U' else (-t if d == 'D' else 0)
        x_min = min(x_min, x + dx)
        x_max = max(x_max, x + dx)
        y_min = min(y_min, y + dy)
        y_max = max(y_max, y + dy)
    return (x_max - x_min) * (y_max - y_min)


def main():
    N = int(input())
    point_list = list()
    x_min, y_min, x_max, y_max = INF, INF, -INF, -INF
    for _ in range(N):
        X, Y, D = input().split()
        X = int(X)
        x_min = min(x_min, X)
        x_max = max(x_max, X)
        Y = int(Y)
        y_min = min(y_min, Y)
        y_max = max(y_max, Y)
        point_list.append((X, Y, D))
    if N == 1:
        print(0)
        return
    t_left, t_right = 0, 2 * max(x_max - x_min, y_max - y_min)
    v_left, v_right = calc(point_list, t_left), calc(point_list, t_right)
    while True:
        dt = t_right - t_left
        if dt < 10 ** (-8):
            break
        t_in_left, t_in_right = t_left + dt / 3, t_right - dt / 3
        v_in_left, v_in_right = calc(point_list, t_in_left), calc(point_list, t_in_right)
        if v_in_left < v_in_right:
            t_right = t_in_right
            v_right = v_in_right
        else:
            t_left = t_in_left
            v_left = v_in_left
    print(v_left)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
INF = 10 ** 9


def calc(point_list, t):
    x_min, y_min, x_max, y_max = INF, INF, -INF, -INF
    for point in point_list:
        x, y, d = point
        dx = t if d == 'R' else (-t if d == 'L' else 0)
        dy = t if d == 'U' else (-t if d == 'D' else 0)
        x_min = min(x_min, x + dx)
        x_max = max(x_max, x + dx)
        y_min = min(y_min, y + dy)
        y_max = max(y_max, y + dy)
    return (x_max - x_min) * (y_max - y_min)


def main():
    N = int(input())
    point_list = list()
    x_min, y_min, x_max, y_max = INF, INF, -INF, -INF
    for _ in range(N):
        X, Y, D = input().split()
        X = int(X)
        x_min = min(x_min, X)
        x_max = max(x_max, X)
        Y = int(Y)
        y_min = min(y_min, Y)
        y_max = max(y_max, Y)
        point_list.append((X, Y, D))
    t_left, t_right = 0, max(x_max - x_min, y_max - y_max)
    while t_right - t_left > 10 ** (-8):
        t_in_left, t_in_right = (2 * t_left + t_right) / 3, (t_left + 2 * t_right) / 3
        if calc(point_list, t_in_left) < calc(point_list, t_in_right):
            t_right = t_in_right
        else:
            t_left = t_in_left
    print(calc(point_list, (t_in_left + t_in_right) / 2))


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

Fixed submission:
from collections import defaultdict
import sys

sys.setrecursionlimit(100000)


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(M):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
    dp = [-1 for _ in range(N)]

    def rec(v):
        if dp[v] >= 0:
            return dp[v]
        ret = 0
        for nv in adj_nodes[v]:
            ret = max([ret, rec(nv) + 1])
        dp[v] = ret
        return ret

    ans = 0
    for v in range(N):
        ans = max([ans, rec(v)])
    print(ans)


if __name__ == '__main__':
    main()

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


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    for _ in range(M):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
    dp = [-1 for _ in range(N)]

    def rec(v):
        if dp[v] >= 0:
            return dp[v]
        ret = 0
        for nv in adj_nodes[v]:
            ret = max([ret, rec(nv) + 1])
        dp[v] = ret
        return ret

    ans = 0
    for v in range(N):
        ans = max([ans, rec(v)])
    print(ans)


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

Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(N)] for _ in range(N)]
    for length in range(1, N + 1):
        for left in range(N - length + 1):
            right = left + length - 1
            val = 0
            if left == right:
                val = A[left]
            else:
                val = max([
                    A[left] - dp[left + 1][right],
                    A[right] - dp[left][right - 1]
                ])
            dp[left][right] = val
    print(dp[0][N - 1])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    dp = [[None for _ in range(N)] for _ in range(N)]

    def rec(sign, left, right):
        ret = dp[left][right]
        if ret is not None:
            return ret
        if left == right:
            val = sign * A[left]
            dp[left][right] = val
            return val
        score_left = sign * A[left] + rec(- sign, left + 1, right)
        score_right = sign * A[right] + rec(- sign, left, right - 1)
        score = max([score_left, score_right]) if sign == 1 else min([score_left, score_right])
        dp[left][right] = score
        return score

    print(rec(1, 0, N - 1))


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

Fixed submission:
import sys
from collections import defaultdict


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
        adj_nodes[y].append(x)
    dp_b = [0 for _ in range(N)]
    dp_w = [0 for _ in range(N)]

    def bfs(node, parent):
        black = 1
        white = 1
        for child in adj_nodes[node]:
            if child == parent:
                continue
            bfs(child, node)
            black *= dp_w[child]
            white *= dp_b[child] + dp_w[child]
            black %= MOD
            white %= MOD
        dp_b[node] = black
        dp_w[node] = white

    bfs(0, None)
    print((dp_b[0] + dp_w[0]) % MOD)


if __name__ == '__main__':
    main()

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


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
        adj_nodes[y].append(x)
    dp_b = [0 for _ in range(N)]
    dp_w = [0 for _ in range(N)]

    def bfs(node, parent):
        black = 1
        white = 1
        for child in adj_nodes[node]:
            if child == parent:
                continue
            bfs(child, node)
            black *= dp_w[child]
            white *= dp_b[child] + dp_w[child]
            black %= MOD
            white %= MOD
        dp_b[node] = black
        dp_w[node] = white

    bfs(0, None)
    print(dp_b[0] + dp_w[0])


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

Fixed submission:
def f(n):
    # prime factorization of n!
    pf = [0 for _ in range(n + 1)]
    for i in range(2, n + 1):
        cur = i
        for j in range(2, i + 1):
            while cur % j == 0:
                pf[j] += 1
                cur //= j
    return pf


def num(m, pf):
    return len(list(filter(lambda x: x >= m - 1, pf)))


def main():
    N = int(input())
    pf = f(N)
    ans = num(75, pf)
    ans += num(25, pf) * (num(3, pf) - 1)
    ans += num(15, pf) * (num(5, pf) - 1)
    ans += num(5, pf) * (num(5, pf) - 1) * (num(3, pf) - 2) // 2
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def f(n):
    # prime factorization of n!
    pf = [0 for _ in range(2, n + 1)]
    for i in range(1, n + 1):
        cur = i
        for j in range(2, i + 1):
            while cur % j == 0:
                pf[j] += 1
                cur //= j
    return pf


def num(m, pf):
    return len(list(filter(lambda x: x >= m - 1, pf)))


def main():
    N = int(input())
    pf = f(N)
    ans = num(75, pf)
    ans += num(25, pf) * (num(3, pf) - 1)
    ans += num(15, pf) * (num(5, pf) - 1)
    ans += num(5, pf) * (num(5, pf) - 1) * (num(3, pf) - 2) // 2
    print(ans)


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

Fixed submission:
def search_center(xyh_list):
    xyh_list.sort(key=lambda r: r[2], reverse=True)
    highest = xyh_list[0]
    for cx in range(101):
        for cy in range(101):
            h = highest[2] + abs(highest[0] - cx) + abs(highest[1] - cy)
            matched = True
            for xyh in xyh_list[1:]:
                if xyh[2] == 0:
                    if h - abs(xyh[0] - cx) - abs(xyh[1] - cy) > 0:
                        matched = False
                        break
                else:
                    hh = xyh[2] + abs(xyh[0] - cx) + abs(xyh[1] - cy)
                    if h != hh:
                        matched = False
                        break
            if matched:
                return cx, cy, h
    return None


def main():
    N = int(input())
    xyh_list = [list(map(int, input().split(' '))) for _ in range(N)]
    xyh_list.sort(key=lambda r: r[2], reverse=True)
    cx, cy, ph = search_center(xyh_list)
    print('{} {} {}'.format(cx, cy, ph))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def search_center(xyh_list):
    xyh_list.sort(key=lambda r: r[2], reverse=True)
    highest = xyh_list[0]
    for cx in range(101):
        for cy in range(101):
            h = highest[2] + abs(highest[0] - cx) + abs(highest[1] - cy)
            matched = True
            for xyh in xyh_list[1:]:
                if xyh[2] == 0:
                    if h - abs(highest[0] - cx) - abs(highest[1] - cy) > 0:
                        matched = False
                        break
                else:
                    hh = xyh[2] + abs(xyh[0] - cx) + abs(xyh[1] - cy)
                    if h != hh:
                        matched = False
                        break
            if matched:
                return cx, cy, h
    return None


def main():
    N = int(input())
    xyh_list = [list(map(int, input().split(' '))) for _ in range(N)]
    xyh_list.sort(key=lambda r: r[2], reverse=True)
    cx, cy, ph = search_center(xyh_list)
    print('{} {} {}'.format(cx, cy, ph))


if __name__ == '__main__':
    main()