Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())

D = dict()
for a in A:
    if a not in D.keys():
        D[a] = 0
    D[a] += 1

for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    
    if B in D.keys():
        if C not in D.keys():
            D[C] = 0
        D[C] += D[B]
        del D[B]

    ans = 0
    for k, v in D.items():
        ans += k * v
    print(ans)



Fixed submission:
N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())

D = dict()
for a in A:
    if a not in D.keys():
        D[a] = 0
    D[a] += 1

ans = 0
for k, v in D.items():
    ans += k * v
    
for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    
    if B in D.keys():
        count = D[B]
        
        if C not in D.keys():
            D[C] = 0
        D[C] += count
        del D[B]
        
        ans += (C - B) * count

    print(ans)
Buggy python submission (verdict: Runtime Error):
h,a = map(input().split())

print((h+a-1)//a)

Fixed submission:
h,a = map(int, input().split())

print((h+a-1)//a)
Buggy python submission (verdict: Runtime Error):
def solve():
    N = int(input())
    S = input()

    AW = [0]*(N+1)
    AE = [0]*(N)

    wcount = 0
    ecount = 0
    for i in range(N):
        if S[i] == "W":
            wcount += 1
        else:
            ecount += 1
        AW[i] = wcount
        AE[i] = ecount

    MIN = 1000000

    for i in range(N):
        tmp = 0
        tmp += AW[i-1]
        tmp += AE[-1] - AE[i]
        MIN = min(MIN, tmp)
    print(MIN)

if __name__ == "__main__":
    local_test()
    solve()

Fixed submission:
def solve():
    N = int(input())
    S = input()

    AW = [0]*(N+1)
    AE = [0]*(N)

    wcount = 0
    ecount = 0
    for i in range(N):
        if S[i] == "W":
            wcount += 1
        else:
            ecount += 1
        AW[i] = wcount
        AE[i] = ecount

    MIN = 1000000

    for i in range(N):
        tmp = 0
        tmp += AW[i-1]
        tmp += AE[-1] - AE[i]
        MIN = min(MIN, tmp)
    print(MIN)

if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
import os
import time
import re
from pydoc import help
import string
import math
import numpy as np
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


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

    CS = [0]*(N+1)

    for n in range(N):
        if n >= 1:
            CS[n+1] = CS[n] + A[n]
        else:
            CS[n+1] = A[n]

    res = 0
    for v in Counter(CS).values():
        if v >= 2:
            res += v*(v-1)//2

    print(res)

if __name__ == "__main__":
    local_test()
    solve()



Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

IN = 'sample-1.in'  # sample case for local test
def local_test():
    try:
        from pcm.utils import set_stdin
        import sys
        import os
        if len(sys.argv) == 1:
            set_stdin(os.path.dirname(__file__) + '/test/' + IN)
    except:
        pass


import sys
import os
import time
import re
from pydoc import help
import string
import math
import numpy as np
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]


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

    CS = [0]*(N+1)

    for n in range(N):
        if n >= 1:
            CS[n+1] = CS[n] + A[n]
        else:
            CS[n+1] = A[n]

    res = 0
    for v in Counter(CS).values():
        if v >= 2:
            res += v*(v-1)//2

    print(res)

if __name__ == "__main__":
    local_test()
    solve()
Buggy python submission (verdict: Runtime Error):
s = input()
 
print(2018 + s[5:])

Fixed submission:
s = input()
 
print('2018' + s[4:])

Buggy python submission (verdict: Runtime Error):
s = int(input())

print(2018 + s[5:])

Fixed submission:
s = input()
 
print('2018' + s[4:])
Buggy python submission (verdict: Runtime Error):
# input
N, Y = map(int, input().split())

def solve():
    y = Y//1000
    if Y%1000 != 0:
        print('-1 -1 -1')
        return

    dp = DP(N, y+1, False)
    dp[0][1] = [1,0,0]
    dp[0][5] = [0,1,0]
    dp[0][10] = [0,0,1]

    for n in range(N-1):
        for m in range(y):
            if m+1 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+1] = tmp
                dp[n+1][m+1][0] += 1
            if m+5 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+5] = tmp
                dp[n+1][m+5][1] += 1
            if m+10 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+10] = tmp
                dp[n+1][m+10][2] += 1

    if dp[N-1][y]:
        print(' '.join(map(str, dp[N-1][y][::-1])))
    else:
        print('-1 -1 -1')


if __name__ == "__main__":
    solve()


Fixed submission:
# input
N, Y = map(int, input().split())

def solve():
    y = Y//1000
    if Y%1000 != 0:
        print('-1 -1 -1')
        return

    flag = False
    for i in range(2*10**3+1):
        for j in range(10**3+1):
            if y - 10*i - 5*j == N - i - j and N-i-j >= 0:
                print(i, j, N - i - j)
                return

    print('-1 -1 -1')


if __name__ == "__main__":
    solve()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(lambda x: int(x)-1, input().split())))


    BC = []
    for i in range(N):
        b = B[i]
        BC.append(N - bisect_left(C, b))

    Cum = []
    S = sum(BC)
    tmp = S
    for i in range(N):
        Cum.append(tmp)
        tmp -= BC[i]
    Cum.append(0)

    count = 0
    for i in range(N):
        a = A[i]
        count += Cum[bisect_right(B, a)]

    print(count)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right, insort_left, insort_right

def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(lambda x: int(x)-1, input().split())))


    BC = []
    for i in range(N):
        b = B[i]
        BC.append(N - bisect_left(C, b))

    Cum = []
    S = sum(BC)
    tmp = S
    for i in range(N):
        Cum.append(tmp)
        tmp -= BC[i]
    Cum.append(0)

    count = 0
    for i in range(N):
        a = A[i]
        count += Cum[bisect_right(B, a)]

    print(count)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())

    MAP = [[0]*N for n in range(N)]

    for m in range(M):
        a, b = map(int, input().split())
        MAP[a-1][b-1] = 1
        MAP[b-1][a-1] = 1

    for first in range(N):
        if MAP[0][first]==1 and MAP[first][N-1] == 1:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Fixed submission:
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    D = dd(list)

    for m in range(M):
        a, b = map(int, input().split())
        D[a-1].append(b-1)

    for d in D[0]:
        if N-1 in D[d]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())

    tree = [[] for i in range(N)]
    for n in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        tree[a].append(b)
        tree[b].append(a)

    # print(np.array(tree))

    Q = [(x, [0, x], 0) for x in tree[0]]
    reached = [1] + [0]*(N-2) + [0]
    while len(Q) > 0:
        new_pos, root, cost = Q.pop()
        reached[new_pos] = 1

        if new_pos == N-1:
            break

        #add to Q
        for p in tree[new_pos]:
            new_root = root[:]
            if reached[p] == 0:
                new_root.append(p)
                Q.append((p, new_root, cost+1))

    l = math.ceil(len(root)/2) - 1
    r = l + 1

    # print(root, l, r)
    tree[root[l]].remove(root[r])
    tree[root[r]].remove(root[l])
    # print(tree, tree)

    F = tree[0]
    S = tree[N-1]

    reached = [1] + [0]*(N-2) + [1]
    while True:
        if len(F) == 0:
            print("Snuke")
            break
        else:
            pos = F.pop()
            reached[pos] = 1
            for p in tree[pos]:
                if reached[p] == 0:
                    F.append(p)

        if len(S) == 0:
            print("Fennec")
            break
        else:
            pos = S.pop()
            reached[pos] = 1
            for p in tree[pos]:
                if reached[p] == 0:
                    S.append(p)



if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()


Fixed submission:
def main():
    A, B = map(int, input().split())

    if (A%3 == 0) or (B%3 == 0) or ((A+B)%3 == 0):
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    L = list(map(int, input().split()))
    L.sort(reverse=True)

    print(sum(L[:K]))

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()



Fixed submission:
def main():
    A, B = map(int, input().split())

    if (A%3 == 0) or (B%3 == 0) or ((A+B)%3 == 0):
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()
Buggy python submission (verdict: Runtime Error):
from copy import deepcopy as dcopy
import fractions
def main():
    global N, ma, mb
    N, ma, mb = map(int, input().split())
    shop = [list(map(int, input().split())) for n in range(N)]

    status = dd(int)
    status[(0,0)] = 0
    minimum = 100000
    for product in shop:
        # buy
        old_status = dcopy(status)
        for s, v in old_status.items():
            key = (s[0]+product[0], s[1]+product[1])
            value = v + product[2]
            if not key in status:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value
            elif status[key] > value:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value

    if minimum == 100000:
        print(-1)
    else:
        print(minimum)

def check(key):
    c = fractions.gcd(key[0], key[1])
    if key[0]/c == ma and key[1]/c == mb:
        return True
    else:
        return False

if __name__ == "__main__":# {{{
    try:
        import test
        test.test()
    except:
        main()# }}}


Fixed submission:
# coding: utf-8

import re
from scipy import integrate
import math
from operator import itemgetter
from collections import defaultdict as dd
from collections import Counter
from collections import deque

import numpy as np
import itertools

import heapq

from copy import deepcopy as dcopy
import fractions
def main():
    global N, ma, mb
    N, ma, mb = map(int, input().split())
    shop = [list(map(int, input().split())) for n in range(N)]

    status = dd(int)
    status[(0,0)] = 0
    minimum = 100000
    for product in shop:
        # buy
        old_status = dcopy(status)
        for s, v in old_status.items():
            key = (s[0]+product[0], s[1]+product[1])
            value = v + product[2]
            if not key in status:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value
            elif status[key] > value:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value

    if minimum == 100000:
        print(-1)
    else:
        print(minimum)

def check(key):
    c = fractions.gcd(key[0], key[1])
    if key[0]/c == ma and key[1]/c == mb:
        return True
    else:
        return False

if __name__ == "__main__":# {{{
    try:
        import test
        test.test()
    except:
        main()# }}}
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import numpy as np

H,N = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0]*N]
M = np.array(M)

def main(h,n,m):
    dp = [10**8+1]*(10**4+1)
    dp = np.array(dp)
    dp[0] = 0

    for i in range(1,10**4+1):
        for j in range(n):
            a = m[j][0]
            b = m[j][1]
            if a>i:
                dp[i] = min(dp[i],b)
            else:
                dp[i] = min(dp[i],dp[i-a]+b)

    print(dp[h])

if __name__=="__main__":
    main(H,N,M)

Fixed submission:
from sys import stdin
import numpy as np
from numba import njit

H,N = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0]*N]
M = np.array(M)

@njit
def main(h,n,m):
    dp = [10**8+1]*(10**4+1)
    dp = np.array(dp)
    dp[0] = 0

    for i in range(1,10**4+1):
        for j in range(n):
            a = m[j][0]
            b = m[j][1]
            if a>i:
                dp[i] = min(dp[i],b)
            else:
                dp[i] = min(dp[i],dp[i-a]+b)

    print(dp[h])

if __name__=="__main__":
    main(H,N,M)
Buggy python submission (verdict: Runtime Error):
from sys import stdin
import copy

n = int(input())
S = [stdin.readline()[:-1] for i in [0]*(n-1)]
S.append(stdin.readline())
s = []
for i in S:
    s.append("".join(sorted(i)))
s.sort()
arr = []
temp = 1
for i in range(n-1):
    if temp>1 and s[i]!=s[i+1]:
        arr.append(temp)
        temp = 1
    if s[i]==s[i+1]:
        temp += 1
if temp>1:
    arr.append(temp)
arr.sort()
factorial = [1]
for i in range(arr[-1]+1):
    factorial.append(factorial[i]*(i+1))
comb = [0,0]
for i in range(2,arr[-1]+1):
    comb.append(factorial[i]/(2*factorial[i-2]))
ans = 0
for i in arr:
    ans += comb[i]
print(int(ans))

Fixed submission:
from sys import stdin
import copy

n = int(input())
S = [stdin.readline()[:-1] for i in [0]*(n)]
#S.append(stdin.readline())
s = []
for i in S:
    s.append("".join(sorted(i)))
s.sort()
arr = []
temp = 1
for i in range(n-1):
    if temp>1 and s[i]!=s[i+1]:
        arr.append(temp)
        temp = 1
    if s[i]==s[i+1]:
        temp += 1
if temp>1:
    arr.append(temp)

ans = 0
for i in arr:
    ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)

Fixed submission:
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)
Buggy python submission (verdict: Runtime Error):
from copy import deepcopy

def getval():
    n = int(input())
    return n

def main(n):
    mod = 10**9 + 7
    #A:0 C:1 G:2 T:3
    dp = [[[1 for i in range(4)] for i in range(4)] for i in range(4)]
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0

    def pow4(arr):
        ans = 0
        for i in range(4):
            ans += arr[i]*(4**(3-i))
        return ans 

    p = []
    for i in range(4):
        p.append(pow4([0,2,1,i]))
        p.append(pow4([0,1,2,i]))
        p.append(pow4([2,0,1,i]))
        p.append(pow4([i,0,2,1]))
        p.append(pow4([i,0,1,2]))
        p.append(pow4([i,2,0,1]))
        p.append(pow4([0,i,2,1]))
        p.append(pow4([0,2,i,1]))

    it1 = iter(p)
    it2 = iter(p)
    co = 0
    di = dict(zip(it1,it2))
    for i in range(n-3):
        temp = [[[0 for i in range(4)] for i in range(4)] for i in range(4)]
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for d in range(4):
                        if pow4([a,b,c,d]) in di:
                            temp[b][c][d] += 0
                        else:
                            temp[b][c][d] += dp[a][b][c]
                            temp[b][c][d] %= mod
        dp = temp

    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans += temp[i][j][k]
    ans %= mod
    print(ans)

if __name__=="__main__":
    n = getval()
    main(n)

Fixed submission:
from copy import deepcopy

def getval():
    n = int(input())
    return n

def main(n):
    mod = 10**9 + 7
    #A:0 C:1 G:2 T:3
    dp = [[[1 for i in range(4)] for i in range(4)] for i in range(4)]
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0

    def pow4(arr):
        ans = 0
        for i in range(4):
            ans += arr[i]*(4**(3-i))
        return ans 

    p = []
    for i in range(4):
        p.append(pow4([0,2,1,i]))
        p.append(pow4([0,1,2,i]))
        p.append(pow4([2,0,1,i]))
        p.append(pow4([i,0,2,1]))
        p.append(pow4([i,0,1,2]))
        p.append(pow4([i,2,0,1]))
        p.append(pow4([0,i,2,1]))
        p.append(pow4([0,2,i,1]))

    it1 = iter(p)
    it2 = iter(p)
    co = 0
    di = dict(zip(it1,it2))
    for i in range(n-3):
        temp = [[[0 for i in range(4)] for i in range(4)] for i in range(4)]
        for a in range(4):
            for b in range(4):
                for c in range(4):
                    for d in range(4):
                        if pow4([a,b,c,d]) in di:
                            temp[b][c][d] += 0
                        else:
                            temp[b][c][d] += dp[a][b][c]
                            temp[b][c][d] %= mod
        dp = temp

    ans = 0
    if n>=4:
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    ans += temp[i][j][k]
    elif n==3:
        ans = 61
    ans %= mod
    print(ans)

if __name__=="__main__":
    n = getval()
    main(n)
Buggy python submission (verdict: Time Limit Exceeded):
def getval():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    return n,k,h 

def main(n,k,h):
    if k>=n-1:
        print(abs(h[-1]-h[0]))
    else:
        dp = [abs(h[i]-h[0]) for i in range(k)]
        for i in range(n):
            if len(dp)<n:
                dp.append(dp[i]+abs(h[i]-h[i+k]))
            for j in range(k-1):
                if i+j+1>=n:
                    break
                dp[i+j+1] = min(dp[i+j+1],dp[i]+abs(h[i]-h[i+j+1]))
        print(dp[-1])

if __name__=="__main__":
    n,k,h = getval()
    main(n,k,h)


Fixed submission:
def getval():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    return n,k,h 

def main(n,k,h):
    if k>=n-1:
        print(abs(h[-1]-h[0]))
    else:
        dp = [abs(h[i]-h[0]) for i in range(k)]
        for i in range(n):
            if len(dp)<n:
                dp.append(dp[i]+abs(h[i]-h[i+k]))
            for j in range(k-1):
                if i+j+1>=n:
                    break
                dp[i+j+1] = min(dp[i+j+1],dp[i]+abs(h[i]-h[i+j+1]))
        print(dp[-1])

if __name__=="__main__":
    n,k,h = getval()
    main(n,k,h)