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

Fixed submission:

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    n, k = input_int_list()
    segtree = SegTree(500000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(500000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)


def main():
    n, k = input_int_list()
    segtree = SegTree(300000)
    for _ in range(n):
        a = input_int()

        val = segtree.fold(max(0, a - k), min(300000, a + k + 1))
        segtree.set_val(a, val + 1)

    print(segtree.X[1])

    return


if __name__ == "__main__":
    main()
Problem p02584 (python)

Fixed submission:

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    x, k, d = [int(i) for i in input().strip().split()]
    div = x // d
    L = x - d * k
    R = x + d * k
    if L >= 0:
        print(L)
        return
    if R < 0:
        print(-R)
        return
    if k <= div:
        ans = x - (d * k)
    else:
        k = k - div
        even = x % d
        odd = abs(d - even)
        if k % 2 == 1:
            ans = odd
        else:
            ans = even
    print(ans)
    return


if __name__ == "__main__":
    main()

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


def main():
    x, k, d = [int(i) for i in input().strip().split()]
    div = x // d
    if x <= d:
        even = x
        odd = abs(x - d)
        if k % 2 == 0:
            ans = even
        else:
            ans = odd
    else:
        if k <= div:
            ans = x - (d * k)
        else:
            k = k - div
            even = x % d
            odd = abs(d - even)
            if even == odd:
                ans = even
            elif k % 2 == 1 and odd < even:
                ans = odd
            elif k % 2 == 0 and even < odd:
                ans = even
    print(ans)
    return


if __name__ == "__main__":
    main()
Problem p02608 (python)

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def checker():
    ans = [0] * 10001
    for a in range(1, 101):
        for b in range(1, 101):
            for c in range(1, 101):
                n = a * a + b * b + c * c + a * b + b * c + c * a
                if n > 10000:
                    continue
                else:
                    ans[n] += 1
    return ans


def main():
    N = int(input().strip())
    ans = checker()
    for n in range(1, N + 1):
        print(ans[n])
    return


if __name__ == "__main__":
    main()

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

table = [0] * 1001

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            k = (x * x) + (y * y) + (z * z) + (x * y) + (y * z) + (z * x)
            if k < 1001:
                table[k] += 1

for i in range(1, n + 1):
    print(table[i])

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


def checker():
    ans = [0] * 10000
    for a in range(1, 101):
        for b in range(1, 101):
            for c in range(1, 101):
                n = a * a + b * b + c * c + a * b + b * c + c * a
                if n > 10000:
                    continue
                else:
                    ans[n] += 1
    return ans


def main():
    N = int(input().strip())
    ans = checker()
    for n in range(1, N + 1):
        print(ans[n])
    return


if __name__ == "__main__":
    main()
Problem p02642 (python)

Fixed submission:
import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)

    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1

    for n in l:
        if dp[n] == 1:
            ans += 1

    return ans


if __name__ == "__main__":
    print(main())

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


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    for i, n in enumerate(l[:-1]):
        flag = False
        if not n:
            continue
        for j, m in enumerate(l[i + 1:]):
            if not m:
                continue
            if m == n:
                flag = True
            if m % n == 0:
                l[i + j + 1] = None
        if flag:
            l[i] = None
    l = set(l)
    l.remove(None)
    ans = len(set(l))

    return ans


if __name__ == "__main__":
    print(main())
Problem p02660 (python)

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                selected.add(factor[0]**counter)
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())
Problem p02664 (python)

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    S = input().strip()
    return S.replace("?","D")

if __name__ == "__main__":
    print(main())

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

def main():
    S = int(input().strip())
    return S.replace("?","D")

if __name__ == "__main__":
    print(main())
Problem p02761 (python)

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    ans = [0 for _ in range(N)]
    if N > 1:
        ans[0] = 1
    for i, s in enumerate(S):
        if s[0] == 1 and s[1] == 0:
            if N > 1:
                print(-1)
                return
        for i2, s2 in enumerate(S):
            if i == i2:
                continue
            if s[0] == s2[0]:
                if s[1] != s2[1]:
                    print(-1)
                    return
        ans[s[0] - 1] = s[1]
    ans = int(''.join([str(n) for n in ans]))
    print(ans)
    return


if __name__ == '__main__':
    main()

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

def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    ans = [0 for _ in range(N)]
    if N > 1:
        ans[0] = 1
    for i, s in enumerate(S):
        if s[0] == 1 and s[1] == 0:
            if N > 1:
                print(-1)
                return
        for i2, s2 in enumerate(S):
            if i == i2:
                continue
            if s[0] == s2[0]:
                if s[1] != s2[1]:
                    print(-1)
                    return
        ANS[s[0] - 1] = s[1]
    ans = int(''.join([str(n) for n in ANS]))
    print(ans)
    return
 
 
if __name__ == '__main__':
    main()
Problem p02801 (python)

Fixed submission:
c = input()
print(chr(ord(c)+1))

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
from copy import deepcopy
input = sys.stdin.readline


def bfs(table, i, j):
    dq = deque()
    if table[i][j] == "#":
        return -1
    h = len(table)
    w = len(table[0])
    ans = 0
    dq.append((i, j, 0))  # x,y,distance
    while dq:
        x, y, dis = dq.popleft()
        ans = max(ans, dis)
        if x > 0 and (x - 1, y) and table[x - 1][y] != "#":
            dq.append((x - 1, y, dis + 1))
            table[x - 1][y] = "#"
        if x < h - 1 and (x + 1, y) and table[x + 1][y] != "#":
            dq.append((x + 1, y, dis + 1))
            table[x + 1][y] = "#"
        if y > 0 and (x, y - 1) and table[x][y - 1] != "#":
            dq.append((x, y - 1, dis + 1))
            table[x][y - 1] = "#"
        if y < w - 1 and (x, y + 1) and table[x][y + 1] != "#":
            dq.append((x, y + 1, dis + 1))
            table[x][y + 1] = "#"
    return ans


def main():
    h, w = [int(i) for i in input().strip().split()]
    grid = [list(input().strip()) for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                _grid = deepcopy(grid)
                max_path = bfs(_grid, i, j)
                ans = max(ans, max_path)

    print(ans)


if __name__ == "__main__":
    main()
Problem p02823 (python)

Fixed submission:
import sys
input = sys.stdin.readline


def main():
    n,a,b = [int(i) for i in input().strip().split()]
    if (b-a) % 2 == 0:
        print(abs(b - a) // 2)
    else:
        ans = min(a - 1, n - b) + 1 + (b - a - 1) // 2
        print(ans)
    return 



if __name__ == "__main__":
    main()

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


def main():
    n,a,b = [int(i) for i in input().strip().split()]
    if abs(a - b) % 2 == 0:
        print(abs(a - b) // 2)
    else:
        ans = min(a - 1, n - b) - 1 + (A - B - 1) // 2
        print(ans)
    return 



if __name__ == "__main__":
    main()
Problem p02900 (python)

Fixed submission:
from fractions import gcd
import copy


def coprime2(a, b):
    return gcd(a, b) == 1


def main():
    A, B = [int(i) for i in input().split()]

    A_l = divisor(A)
    B_l = divisor(B)
    AB_l = set()
    for a in A_l:
        if a in B_l:
            AB_l.add(a)
    AB_l = sorted(list(AB_l))
    tmp = set(AB_l)
    ans = []
    for i, a in enumerate(AB_l):
        if a not in tmp:
            continue
        try:
            tmp.remove(a)
        except:
            pass
        for b in list(tmp):
            if gcd(a, b) != 1:
                try:
                    tmp.remove(b)
                except:
                    pass
        else:
            ans.append(a)

    print(len(ans))


def divisor(n):
    i = 1
    table = set()
    while i * i <= n:
        if n % i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table


if __name__ == "__main__":
    main()

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

def main():
    A, B = [int(i) for i in input().split()]

    G = gcd(A, B)
    factor = set()
    for i in range(2, G + 1):
        while G % i == 0:
            factor.add(i)
            G = G // i
    print(len(list(factor))+1)


if __name__ == "__main__":
    main()
Problem p02911 (python)

Fixed submission:
from collections import Counter

def main():
    N, K, Q = [int(i) for i in input().split()]
    Submits = Counter([int(input()) for _ in range(Q)])
    for n in range(1, N + 1):
        try:
            if K - Q + Submits[n] > 0:
                print("Yes")
            else:
                print("No")
        except:
            print("No")


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K, Q = [int(i) for i in input().split()]
    L = [0] * N
    Submits = [int(input()) for _ in range(Q)]

    for submit in Submits:
        L[submit] =  L[submit] + 1
    
    for chk in L:
        if K - Q + chk > 0:
            print("Yes")
        else:
            print("No")



if __name__ == "__main__":
    main()
Problem p03160 (python)

Fixed submission:
class Solver():
    def __init__(self, N, costs):
        self.dp = [-1] * N
        self.dp[0] = 0
        self.costs = costs

    def solve(self):
        for i in range(1, len(self.costs)):
            if i == 1:
                self.dp[i] = abs(self.costs[i]-self.costs[i-1])
                continue
            self.dp[i] = min(self.dp[i - 1] + abs(self.costs[i] - self.costs[i-1]),
                        self.dp[i - 2] + abs(self.costs[i] - self.costs[i-2]))

        return self.dp[-1]


def main():
    N = int(input())
    costs = [int(i) for i in input().split()]
    solver = Solver(N, costs)
    print(solver.solve())


if __name__ == "__main__":
    main()

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


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

    dp = [[0 for _ in range(N)] for _ in range(W + 1)]

    for i in range(N):
        for capacity in range(W + 1):
            if i == 0:
                if capacity >= items[i][0]:
                    dp[capacity][i] = items[i][1]
                else:
                    dp[capacity][i] = 0
            else:
                if capacity >= items[i][0]:
                    dp[capacity][i] = max(
                        dp[capacity][i - 1], dp[capacity - items[i][0]][i - 1] + items[i][1])
                else:
                    dp[capacity][i] = dp[capacity][i-1]

    return dp[-1][-1]


if __name__ == "__main__":
    print(main())
Problem p03163 (python)

Fixed submission:
class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
if __name__ == "__main__":
    print(main())

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None for _ in range(W+1)] for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        if j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()
Problem p03196 (python)

Fixed submission:

def get_prime(N):
    if N < 2:
        return {1:1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1


if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    _tmp = cnt//n
    ans *= p**(cnt//n)

print(ans)

Buggy submission (verdict: Runtime Error):

def get_prime(N):
    if N < 2:
        return {1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1

if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    _tmp = cnt//n
    ans *= p**(cnt//n)

print(ans)

Buggy submission (verdict: Runtime Error):

def get_prime(N):
    if N < 2:
        return {1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1

if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    if cnt >= n:

        ans *= p*(cnt//n)

print(ans)

Buggy submission (verdict: Runtime Error):
def get_prime(N):
    if N < 2:
        return {1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1

if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    if cnt >= n:
        ans *= p

print(ans)
Problem p03231 (python)

Fixed submission:
# https://atcoder.jp/contests/agc028/tasks/agc028_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    _gcd = gcd(m, n)
    size = lcm(m, n)
    S = input()
    T = input()
    if S[::n // _gcd] == T[::m // _gcd]:
        print(size)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/agc028/tasks/agc028_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    size = lcm(m, n)
    X = [None] * (size + 1000)
    S = input()
    T = input()
    try:
        for i in range(n):
            X[i * (size // n) + 1] = S[i]
        for i in range(m):
            if X[i * (size // m) + 1] == T[i]:
                continue
            elif not X[i * (size // m) + 1]:
                X[i * (size // m) + 1] = T[i]
            else:
                print(-1)
                return
        print(size)
    except BaseException:
        print(-1)
    return


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/agc028/tasks/agc028_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    size = lcm(m, n)
    X = [None] * (size + 1)
    S = input()
    T = input()
    for i in range(n):
        X[i * (size // n) + 1] = S[i]
    for i in range(m):
        if X[i * (size // m) + 1] == T[i]:
            continue
        elif not X[i * (size // m) + 1]:
            X[i * (size // m) + 1] = T[i]
        else:
            print(-1)
            return
    print(size)
    return


if __name__ == "__main__":
    main()