Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
total, k = map(int, input().split())

d = input().split()

def find_lowest_denomination(total, d):
    for i in range(total, 10001):
        if not set(str(i)) & set(d):
            print(i)
            return
    raise ValueError('Should never reach this code block')



find_lowest_denomination(total, d)


Fixed submission:
total, k = map(int, input().split())

d = list(map(int, input().split()))

def total_to_digits(total):
    return map(int, list(str(total)))

def find_lowest_denomination(total, d):
    res = None
    for i in range(total, 99999):
        digits = list(total_to_digits(i))
        if not (set(digits) & set(d)):
            print(i)
            return


find_lowest_denomination(total, d)
Buggy python submission (verdict: Runtime Error):
import math

a, b, c= [int(x) for x in input().split()] 

# Atcoder beginner contest 145. A - Circle

r = int(input())

a = (math.pi * (r)**2)
ans = a / math.pi

# the answer must be integer, != float
print(int(ans))

Fixed submission:
import math

r = int(input())

pi = int(math.pi)

a = (pi * (r)**2)
ans = a / pi

print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from math import gcd

    def soinsuu(a):
        yy, j = set(), 2
        y = yy.add
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return yy
    n = int(input())
    a = list(map(int, input().split()))

    s = set()
    flag = False
    for i in a:
        so = soinsuu(i)
        for j in so:
            if j in s:
                flag = True
                break
            else:
                s.add(j)
        if flag:
            break
    if flag == False:
        print("pairwise coprime")
        return

    temp1 = a[0]
    for i in a[1:]:
        temp1 = gcd(temp1, i)
    if temp1 > 1:
        print("not coprime")
    else:
        print("setwise coprime")


main()


Fixed submission:
def main():
    from math import gcd

    def soinsuu(a):
        yy, j = set(), 2
        y = yy.add
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return yy
    n = int(input())
    a = list(map(int, input().split()))

    s = set()
    flag = False
    for i in a:
        so = soinsuu(i)
        for j in so:
            if j in s:
                flag = True
                break
            else:
                s.add(j)
        if flag:
            break
    if flag == False:
        print("pairwise coprime")
        return

    temp1 = a[0]
    for i in a[1:]:
        temp1 = gcd(temp1, i)
    if temp1 > 1:
        print("not coprime")
    else:
        print("setwise coprime")


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "#":
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "#":
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()


Fixed submission:
def main():
    import heapq
    inf = 10**8
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start = (start[0]-1, start[1]-1)
    goal = (goal[0]-1, goal[1]-1)
    grid = [input() for _ in [0]*h]
    dist = [[inf]*w for _ in [0]*h]
    q = [(0, start)]
    dist[start[0]][start[1]] = 0
    heapq.heapify(q)
    while q:
        d, (nowx, nowy) = heapq.heappop(q)
        for i, j in [(nowx-1, nowy), (nowx+1, nowy), (nowx, nowy-1), (nowx, nowy+1)]:
            if i < 0 or i >= h or j < 0 or j >= w:
                continue
            if grid[i][j] == "#":
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                heapq.heappush(q, (d, (i, j)))
        for i in range(nowx-2, nowx+3):
            for j in range(nowy-2, nowy+3):
                if i < 0 or i >= h or j < 0 or j >= w:
                    continue
                if grid[i][j] == "#":
                    continue
                if dist[i][j] > d+1:
                    dist[i][j] = d+1
                    heapq.heappush(q, (d+1, (i, j)))
    if dist[goal[0]][goal[1]] == inf:
        print(-1)
        return
    print(dist[goal[0]][goal[1]])


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()


Fixed submission:
def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    mod = 0
    pow10 = 1
    for i in range(20*n):
        mod = (mod+7*pow10) % n
        if mod == 0:
            print(i+1)
            return
        pow10 = pow10*10 % n
    print(-1)


main()


Fixed submission:
def main():
    n = int(input())
    mod = 0
    pow10 = 1
    for i in range(20*n):
        mod = (mod+7*pow10) % n
        if mod == 0:
            print(i+1)
            return
        pow10 = pow10*10 % n
    print(-1)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    pow_minus = [1 % count_minus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    for i in range(n):
        pow_minus.append(pow_minus[-1]*2 % count_minus)

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    for i in range(n):
        if bit[i] == "1":
            bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
            if count_minus == 0:
                ans.append(0)
                continue
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()

Fixed submission:
def main():
    n = int(input())
    bit = input()[::-1]
    count = bit.count("1")
    count_plus = count+1
    count_minus = count-1
    pow_plus = [1 % count_plus]
    for i in range(n):
        pow_plus.append(pow_plus[-1]*2 % count_plus)
    if count_minus != 0:
        pow_minus = [1 % count_minus]
        for i in range(n):
            pow_minus.append(pow_minus[-1]*2 % count_minus)
    else:
        pow_minus = []

    bit_plus = 0
    bit_minus = 0

    for i in range(n):
        if bit[i] == "1":
            bit_plus = (bit_plus+pow_plus[i]) % count_plus
    if count_minus != 0:
        for i in range(n):
            if bit[i] == "1":
                bit_minus = (bit_minus+pow_minus[i]) % count_minus
    ans = []
    for i in range(n):
        if bit[i] == "1":
            if count_minus == 0:
                ans.append(0)
                continue
            bit_ans = (bit_minus-pow_minus[i]) % count_minus
            count = count_minus
        else:
            bit_ans = (bit_plus+pow_plus[i]) % count_plus
            count = count_plus
        cnt = 1
        while bit_ans:
            b = str(bin(bit_ans)).count("1")
            bit_ans = bit_ans % b
            cnt += 1
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6
    
    for i in range(n):
        x, y = map(int, input().split())
        if x > y:
            y, x = x, y
        ans -= x * (n - y + 1)
    print(ans)
    
main()

Fixed submission:
def main():
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6
    
    for i in range(n-1):
        x, y = map(int, input().split())
        if x > y:
            y, x = x, y
        ans -= x * (n - y + 1)
    print(ans)
    
main()

Buggy python submission (verdict: Runtime Error):
def main() {
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6;
    for i in range(n):
        x, y = map(int, input().split())
        if (x > y) { y, x = x, y; }
        ans -= x * (n - y + 1);
    }
    print(ans);
}
main()

Fixed submission:
def main():
    n = int(input())
    ans = n * (n + 1) * (n + 2) // 6
    
    for i in range(n-1):
        x, y = map(int, input().split())
        if x > y:
            y, x = x, y
        ans -= x * (n - y + 1)
    print(ans)
    
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x, y = a[0], a[1]
    nim = 0
    for i in range(2, n):
        nim ^= a[i]
    ans = 0

    while((x ^ y) != nim):
        for i in range(50, -1, -1):
            j = (nim >> i) & 1
            xy = ((x >> i) ^ (y >> i)) & 1
            if j != xy:
                m = min(x % (2**i)+1, 2**i-(y % (2**i)))
                if x % (2**i)+1 == 2**i-(y % (2**i)):
                    print(-1)
                    return
                x -= m
                y += m
                ans += m
                break
        else:
            if (x ^ y) != nim:
                print(-1)
                return
        if x == 0:
            print(-1)
            return
    print(ans)


main()


Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x, y = a[0], a[1]
    nim = 0
    for i in range(2, n):
        nim ^= a[i]
    ans = 0

    while((x ^ y) != nim):
        for i in range(50, -1, -1):
            j = (nim >> i) & 1
            xy = ((x >> i) ^ (y >> i)) & 1
            if j != xy:
                m = min(x % (2**i)+1, 2**i-(y % (2**i)))
                if x % (2**i)+1 == 2**i-(y % (2**i)):
                    print(-1)
                    return
                x -= m
                y += m
                ans += m
                if x <= 0:
                    print(-1)
                    return
                break
        else:
            if (x ^ y) != nim:
                print(-1)
                return
    print(ans)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x, y = a[0], a[1]
    nim = 0
    for i in range(2, n):
        nim ^= a[i]
    ans = 0

    while((x ^ y) != nim):
        for i in range(50, -1, -1):
            j = (nim >> i) & 1
            xy = ((x >> i) ^ (y >> i)) & 1
            if j != xy:
                m = min(x % (2**i)+1, 2**i-(y % (2**i)))
                if x % (2**i)+1 == 2**i-(y % (2**i)):
                    print(-1)
                    return
                x -= m
                y += m
                ans += m
                break
        if x == 0:
            print(-1)
            return
    print(ans)


main()


Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x, y = a[0], a[1]
    nim = 0
    for i in range(2, n):
        nim ^= a[i]
    ans = 0

    while((x ^ y) != nim):
        for i in range(50, -1, -1):
            j = (nim >> i) & 1
            xy = ((x >> i) ^ (y >> i)) & 1
            if j != xy:
                m = min(x % (2**i)+1, 2**i-(y % (2**i)))
                if x % (2**i)+1 == 2**i-(y % (2**i)):
                    print(-1)
                    return
                x -= m
                y += m
                ans += m
                if x <= 0:
                    print(-1)
                    return
                break
        else:
            if (x ^ y) != nim:
                print(-1)
                return
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    mod = 998244353
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in [0]*(c+1)]
    dp[a][b] = 1
    for i in range(a+b+1, c+d+1):
        for p in range(c, a-1, -1):
            q = i-p
            if q > d:
                break
            if q < 0:
                continue
            dp[p][q] = (q*dp[p-1][q]+p*dp[p][q-1] -
                        (p-1)*(q-1)*dp[p-1][q-1]) % mod
    print(dp[c][d])


main()


Fixed submission:
def main():
    mod = 998244353
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in [0]*(c+1)]
    dp[a][b] = 1
    for i in range(a+b+1, c+d+1):
        for p in range(c, a-1, -1):
            q = i-p
            if q > d:
                break
            if q < 0:
                continue
            dp[p][q] = (q*dp[p-1][q]+p*dp[p][q-1] -
                        (p-1)*(q-1)*dp[p-1][q-1]) % mod
    print(dp[c][d])


main()

Buggy python submission (verdict: Runtime Error):
def main():
    mod = 998244353
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in [0]*(c+1)]
    dp[a][b] = 1
    for i in range(a+b+1, c+d+1):
        for p in range(c, a-1, -1):
            q = i-p
            if q > d:
                break
            dp[p][q] = (q*dp[p-1][q]+p*dp[p][q-1] -
                        (p-1)*(q-1)*dp[p-1][q-1]) % mod
    print(dp[c][d])


main()


Fixed submission:
def main():
    mod = 998244353
    a, b, c, d = map(int, input().split())
    dp = [[0]*(d+1) for _ in [0]*(c+1)]
    dp[a][b] = 1
    for i in range(a+b+1, c+d+1):
        for p in range(c, a-1, -1):
            q = i-p
            if q > d:
                break
            if q < 0:
                continue
            dp[p][q] = (q*dp[p-1][q]+p*dp[p][q-1] -
                        (p-1)*(q-1)*dp[p-1][q-1]) % mod
    print(dp[c][d])


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import Counter as ct
    n = int(input())
    a = ct(list(map(int, input().split())))
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])

    s = set()
    ans = 0
    for i in a3:
        for j in s:
            if i % j == 0:
                break
        else:
            s.add(i)
    for i in a2:
        for j in s:
            if i % j == 0:
                break
        else:
            ans += 1
            s.add(i)
    print(ans)


main()


Fixed submission:

def main():
    from collections import Counter as ct
    n = int(input())
    s = list(map(int, input().split()))
    a = ct(s)
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])
    s = set(s)

    ans = 0
    for i in a3:
        if i in s:
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    for i in a2:
        if i in s:
            ans += 1
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    t = input()
    n = len(t)
    dp = [0, 0]
    DP = ["", ""]
    for i in range(n):
        dp2 = [0, 0]
        DP2 = ["", ""]
        if t[i] == "P":
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
        elif t[i] == "D":
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        else:
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        dp = dp2
        DP = DP2
    if dp[0] >= dp[1]:
        print(DP[0])
    else:
        print(DP[1])


main()

Fixed submission:
def main():
    t = input()
    n = len(t)
    ans = ""
    for i in range(n):
        if t[i] == "?":
            ans += "D"
        else:
            ans += t[i]
    print(ans)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    t = input()
    n = len(t)
    dp = [0, 0]
    DP = ["", ""]
    for i in range(n):
        dp2 = [0, 0]
        DP2 = ["", ""]
        if t[i] == "P":
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
        elif t[i] == "D":
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        else:
            if dp[0] > dp[1]:
                dp2[0] = dp[0]
                DP2[0] = DP[0]+"P"
            else:
                dp2[0] = dp[1]
                DP2[0] = DP[1]+"P"
            if dp[0]+2 >= dp[1]+1:
                dp2[1] = dp[0]+2
                DP2[1] = DP[0]+"D"
            else:
                dp2[1] = dp[1]+1
                DP2[1] = DP[1]+"D"
        dp = dp2
        DP = DP2
    if dp[0] >= dp[1]:
        print(DP[0])
    else:
        print(DP[1])


main()

Fixed submission:
def main():
    t = input()
    n = len(t)
    ans = ""
    for i in range(n):
        if t[i] == "?":
            ans += "D"
        else:
            ans += t[i]
    print(ans)


main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [((i-1)//n, (i-1) % n) for i in a]
    b = [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]
    sit = [[True for j in range(n)] for i in range(n)]
    ans = 0
    for i, j in a:
        sit[i][j] = False
        ans += b[i][j]
        q = [(i, j, b[i][j])]
        while q:
            x, y, z = q.pop()
            if x != 0:
                if b[x-1][y] > z:
                    b[x-1][y] = z
                    q.append((x-1, y, z+sit[x-1][y]))
            if x != n-1:
                if b[x+1][y] > z:
                    b[x+1][y] = z
                    q.append((x+1, y, z+sit[x+1][y]))
            if y != 0:
                if b[x][y-1] > z:
                    b[x][y-1] = z
                    q.append((x, y-1, z+sit[x][y-1]))
            if y != n-1:
                if b[x][y+1] > z:
                    b[x][y+1] = z
                    q.append((x, y+1, z+sit[x][y+1]))
    print(ans)


main()


Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [((i-1)//n, (i-1) % n) for i in a]
    b = [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]
    sit = [[True for j in range(n)] for i in range(n)]
    ans = 0
    for i, j in a:
        sit[i][j] = False
        ans += b[i][j]
        q = [(i, j, b[i][j])]
        while q:
            x, y, z = q.pop()
            if x != 0:
                if b[x-1][y] > z:
                    b[x-1][y] = z
                    q.append((x-1, y, z+sit[x-1][y]))
            if x != n-1:
                if b[x+1][y] > z:
                    b[x+1][y] = z
                    q.append((x+1, y, z+sit[x+1][y]))
            if y != 0:
                if b[x][y-1] > z:
                    b[x][y-1] = z
                    q.append((x, y-1, z+sit[x][y-1]))
            if y != n-1:
                if b[x][y+1] > z:
                    b[x][y+1] = z
                    q.append((x, y+1, z+sit[x][y+1]))
    print(ans)


main()