Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

ans = 0
for x in range(1, N+1):
    term1 = math.floor(A*x/B)
    term2 = A * math.floor(x/B)
    temp = term1 - term2

    # print("x: {}, temp: {}, term1: {}, term2: {}".format(x, temp, term1, term2))

    ans = max(ans, temp)

print(ans)


Fixed submission:
import math

DEBUG = False

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

if DEBUG:
    ans = 0
    for x in range(1, N+1):
        term1 = math.floor(A*x/B)
        term2 = A * math.floor(x/B)
        temp = term1 - term2
        print("x: {}, temp: {}, term1: {}, term2: {}".format(x, temp, term1, term2))
        ans = max(ans, temp)
    print(ans)

print(math.floor(A*min(B-1, N)/B)-A*math.floor(min(B-1, N)/B))

Buggy python submission (verdict: Runtime Error):
import itertools

N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
P = [[i for i in range(1, M+1)] for _ in range(N)]

# print(R)
for comb in itertools.product(*P):
    flag = True
    p = comb[0]
    for i in comb:
        if i < p:
            flag = False
            break
        p = i

    if not flag:
        continue

    # print(comb)

    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

print(ans)


Fixed submission:
import math

DEBUG = False

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

if DEBUG:
    ans = 0
    for x in range(1, N+1):
        term1 = math.floor(A*x/B)
        term2 = A * math.floor(x/B)
        temp = term1 - term2
        print("x: {}, temp: {}, term1: {}, term2: {}".format(x, temp, term1, term2))
        ans = max(ans, temp)
    print(ans)

print(math.floor(A*min(B-1, N)/B)-A*math.floor(min(B-1, N)/B))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
dp = [0] * (len(S)+1)

if int(S[:4]) % 2019 == 0:
    dp[4] += 1

for i in range(5,len(S)+1):
    for j in range(i-4+1):
        # print("i: {}, j:{}".format(i, j))
        # print("string: {}".format(S[i-4-j:i]))
        if int(S[i-4-j:i]) % 2019 == 0:
            dp[i] += 1
    dp[i] += dp[i-1]

print(dp[len(S)])


Fixed submission:
from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)
# print("counter: {}".format(counter))

ans = 0
for v in counter.values():
    ans += v * (v-1) // 2

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
dp = [0] * (len(S)+1)

if int(S[:4]) % 2019 == 0:
    dp[4] += 1

for i in range(5,len(S)+1):
    for j in range(i-4+1):
        # print("i: {}, j:{}".format(i, j))
        # print("string: {}".format(S[i-4-j:i]))
        if int(S[i-4-j:i]) % 2019 == 0:
            dp[i] += 1
    dp[i] += dp[i-1]

print(dp[len(S)])


Fixed submission:
from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)
# print("counter: {}".format(counter))

ans = 0
for v in counter.values():
    ans += v * (v-1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

flags = [-1] * (10**8+7)

count = 0
now = 1
flags[0] = 1
while count != K:
    if now < 10:
        flags[now] = 1
    elif now < 100:
         if abs((now % 10) - (now // 10)) <= 1:
             flags[now] = 1
         else:
             flags[now] = 0
    else:
        n = int(str(now)[1:])
        if len(str(now)[1:]) != len(str(n)):
            if int(str(n)[0]) == 1 or int(str(n)[0]) == 0:
                if flags[n]:
                    if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                        flags[now] = 1
                    else:
                        flags[now] = 0
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
        else:
            if flags[n]:
                if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                    flags[now] = 1
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
    if flags[now] == 1:
        count += 1
        # print(now)
    # print('count: {}, now: {}, flag: {}'.format(count, now, flags[now]))
    now += 1

print(now - 1)


Fixed submission:
from collections import deque

K = int(input())

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

x = 1
count = 0
while K != count:
    x = queue.popleft()
    if (x % 10) != 0:
        queue.append(10 * x + (x % 10) - 1)
    queue.append(10 * x + (x % 10))
    if (x % 10) != 9:
        queue.append(10 * x + (x % 10) + 1)
    count += 1
print(x)

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

flags = [-1] * (10**8+7)

count = 0
now = 1
flags[0] = 1
while count != K:
    if now < 10:
        flags[now] = 1
    elif now < 100:
         if abs((now % 10) - (now // 10)) <= 1:
             flags[now] = 1
         else:
             flags[now] = 0
    else:
        n = int(str(now)[1:])
        if len(str(now)[1:]) != len(str(n)):
            if int(str(n)[0]) == 1 or int(str(n)[0]) == 0:
                if flags[n]:
                    if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                        flags[now] = 1
                    else:
                        flags[now] = 0
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
        else:
            if flags[n]:
                if abs(int(str(now)[0]) - int(str(now)[1])) <= 1:
                    flags[now] = 1
                else:
                    flags[now] = 0
            else:
                flags[now] = 0
    if flags[now] == 1:
        count += 1
        # print(now)
    # print('count: {}, now: {}, flag: {}'.format(count, now, flags[now]))
    now += 1

print(now - 1)


Fixed submission:
from collections import deque

K = int(input())

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

x = 1
count = 0
while K != count:
    x = queue.popleft()
    if (x % 10) != 0:
        queue.append(10 * x + (x % 10) - 1)
    queue.append(10 * x + (x % 10))
    if (x % 10) != 9:
        queue.append(10 * x + (x % 10) + 1)
    count += 1
print(x)
Buggy python submission (verdict: Time Limit Exceeded):
N, X, Y = map(int, input().split())

ans = [0] * (N - 1)
for i in range(N):
    for j in range(i + 1, N):
        dist = min(abs(i - j), abs((X - 1) - i) + abs((Y - 1) - j) + 1, abs((Y - 1) - i) + abs((X - 1) - j) + 1)
        ans[dist - 1] += 1
        # print("i:{}, j:{}, dist:{}".format(i, j, dist))
for k in ans:
    print(k)


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

X -= 1
Y -= 1

ans = [0] * (N - 1)
for i in range(N):
    for j in range(i + 1, N):
        dist = min(abs(i - j), abs(X - i) + abs(Y - j) + 1, abs(Y - i) + abs(X - j) + 1)
        ans[dist - 1] += 1
        # print("i:{}, j:{}, dist:{}".format(i, j, dist))
for k in ans:
    print(k)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import copy
import collections

def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

counter = collections.Counter(A)
dic = {c: comb(counter[c], 2) for c in counter.keys()}

for i in range(N):
    i_comb = comb(counter[A[i]]-1, 2)
    new_dict = copy.deepcopy(dic)
    new_dict[A[i]] = i_comb
    print(sum(new_dict.values()))


Fixed submission:
import math
import collections

def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

counter = collections.Counter(A)
dic = {c: comb(counter[c], 2) for c in counter.keys()}
sum_dic = sum(dic.values())

for i in A:
    print(sum_dic - (counter[i] - 1))

Buggy python submission (verdict: Time Limit Exceeded):
import math
import copy
import collections

def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

counter = collections.Counter(A)
dic = {c: comb(counter[c], 2) for c in counter.keys()}

for i in range(N):
    i_comb = comb(counter[A[i]]-1, 2)
    new_dict = copy.deepcopy(dic)
    new_dict[A[i]] = i_comb
    print(sum(new_dict.values()))


Fixed submission:
import math
import collections

def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

counter = collections.Counter(A)
dic = {c: comb(counter[c], 2) for c in counter.keys()}
sum_dic = sum(dic.values())

for i in A:
    print(sum_dic - (counter[i] - 1))

Buggy python submission (verdict: Time Limit Exceeded):
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

for i in range(N):
    B = A[:i] + A[i+1:]
    ans = 0
    for c in set(B):
        find = len(list(filter(lambda x: x == c, B)))
        # print("c:{}, find:{}".format(c, find))
        if find <= 1:
            ans += 0
        else:
            ans += comb(find, 2)
    print(ans)


Fixed submission:
import math
import collections

def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(r) * (math.factorial(n - r)))

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

counter = collections.Counter(A)
dic = {c: comb(counter[c], 2) for c in counter.keys()}
sum_dic = sum(dic.values())

for i in A:
    print(sum_dic - (counter[i] - 1))
Buggy python submission (verdict: Runtime Error):
N, A, B = int(input())

print(N//(A+B)*B + max(N%(A+B)-A, 0))


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

if A==B==0:
    print(0)
else:
    print(N//(A+B)*A + min(N%(A+B), A))
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
q = int(input())

is_s0_head = True
tail = len(S)-1

for _ in range(q):
    # print(S)
    Q = list(input().split())
    if Q[0] == "1":
        is_s0_head = not is_s0_head
    else:
        if Q[1] == "1":
            if is_s0_head:
                S = Q[2] + S
            else:
                S = S + Q[2]
        else:
            if is_s0_head:
                S = S + Q[2]
            else:
                S = Q[2] + S

if is_s0_head:
    print(S)
else:
    print(S[::-1])


Fixed submission:
from collections import deque

S = input()
q = int(input())

is_s0_head = True
tail = len(S)-1

queue = deque(S)

for _ in range(q):
    # print(queue)
    Q = list(input().split())
    if Q[0] == "1":
        is_s0_head = not is_s0_head
    else:
        if Q[1] == "1":
            if is_s0_head:
                queue.appendleft(Q[2])
            else:
                queue.append(Q[2])
        else:
            if is_s0_head:
                queue.append(Q[2])
            else:
                queue.appendleft(Q[2])

if is_s0_head:
    print("".join(list(queue)))
else:
    print("".join(list(queue)[::-1]))

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
q = int(input())

tail = len(S)-1

for _ in range(q):
    # print(S)
    Q = list(input().split())
    if Q[0] == "1":
        S = S[::-1]
    else:
        if Q[1] == "1":
            S = Q[2] + S
        else:
            S = S + Q[2]
print(S)


Fixed submission:
from collections import deque

S = input()
q = int(input())

is_s0_head = True
tail = len(S)-1

queue = deque(S)

for _ in range(q):
    # print(queue)
    Q = list(input().split())
    if Q[0] == "1":
        is_s0_head = not is_s0_head
    else:
        if Q[1] == "1":
            if is_s0_head:
                queue.appendleft(Q[2])
            else:
                queue.append(Q[2])
        else:
            if is_s0_head:
                queue.append(Q[2])
            else:
                queue.appendleft(Q[2])

if is_s0_head:
    print("".join(list(queue)))
else:
    print("".join(list(queue)[::-1]))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

S = []
C = []

condition = [-1] * M

for _ in range(M):
    s, c = map(int, input().split())
    #S.append(s)
    #C.append(C)
    if condition[s-1] != c and condition[s-1] != -1:
        print('-1')
        exit()
    condition[s-1] = c

for i, v in enumerate(condition):
    if v == -1:
        condition[i] = 0
    print(condition[i], end="")
print()


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

ans = [-1] * N
if N == 1 and M == 0:
    print(0)
    exit(0)
for _ in range(M):
    sn, cn = map(int, input().split())
    if ans[sn - 1] != -1 and ans[sn - 1] != cn:
        print(-1)
        exit(0)
    if sn == 1 and cn == 0 and N > 1:
        print(-1)
        exit(0)
    ans[sn - 1] = cn
if ans[0] == -1:
    ans[0] = 1
ans = list(map(lambda x: str(0) if x == -1 else str(x), ans))
print("".join(ans))

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

S = []
C = []

condition = [-1] * M

for _ in range(M):
    s, c = map(int, input().split())
    #S.append(s)
    #C.append(C)
    if condition[s-1] != c and condition[s-1] != -1:
        print('-1')
        exit()
    condition[s-1] = c

for i, v in enumerate(condition):
    if v == -1:
        condition[i] = 0
    print(condition[i], end="")


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

ans = [-1] * N
if N == 1 and M == 0:
    print(0)
    exit(0)
for _ in range(M):
    sn, cn = map(int, input().split())
    if ans[sn - 1] != -1 and ans[sn - 1] != cn:
        print(-1)
        exit(0)
    if sn == 1 and cn == 0 and N > 1:
        print(-1)
        exit(0)
    ans[sn - 1] = cn
if ans[0] == -1:
    ans[0] = 1
ans = list(map(lambda x: str(0) if x == -1 else str(x), ans))
print("".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))

H_sorted = sorted(H, reverse=True)

for _ in range(K):
    if (not len(H_sorted)):
        break
    H_sorted.pop(0)

print(sum(H_sorted))


Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))

H_sorted = sorted(H, reverse=True)

print(sum(H_sorted[K:]))
Buggy python submission (verdict: Runtime Error):
from inspect import currentframe

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]

    num_vote = M * V
    a = 0
    b = len(C)
    flag = True
    while a < b:
        def is_margin_plus(i):
            v = C[i][1]
            margin = num_vote
            margin -= M * (P-1)
            margin_list = [v+M-w for (j,w) in C if j!=i]
            mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
            margin -= M
            margin -= sum(mod_margin_list)
            # print("margin: {}".format(margin))

            return margin > 0

        i = (a + b) // 2
        # input()
        # print("(a, i, b): ({}, {}, {})".format(a, i, b))

        if is_margin_plus(i):
            # print('is_margin_plus: {}'.format(True))
            b = i
        else:
            # print('is_margin_plus: {}'.format(False))
            a = i + 1
            flag = False

    ans = a + P + 1 if flag else (a + P)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, A, B = map(int, input().split())
    result = N
    if (A % 2 == 0 and B % 2 == 0) or  (A % 2 == 1 and B % 2 == 1):
        result = abs(A - B) // 2
    else:
        if A - 1 < N - B:
            result = ((B - 1) - (A - 1 + 1)) // 2 + (A - 1 + 1)
        else:
            result = ((N - A) - (N - B + 1)) // 2 + (N - B + 1)

    print(int(result))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N % 2 == 1:
    ans = 0
else:
    count = 1
    num5 = 0
    while N//2 >= 5**count:
        num5 += N//(2*5**count)
        count+=1

print(num5)


Fixed submission:
N = int(input())

if N % 2 == 1:
    ans = 0
else:
    count = 1
    ans = 0
    while N//2 >= 5**count:
        ans += N//(2*5**count)
        count+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
xy = []
A = []
for i in range(N):
    Ai = int(input())
    xyi = []
    for j in range(Ai):
        xyi.append(list(map(int, input().split())))
    A.append(Ai)
    xy.append(xyi)

ans = 0

for i in range(2**N):
    bin_i = format(i, '4b')
    flag = True
    for n, c in enumerate(bin_i):
        if c == '1':
            for j in range(N):
                for k in range(A[j]):
                    if xy[j][k][0] == n:
                        if xy[j][k][1] == 0:
                            flag = False
                            break
                if not flag:V
                    break
            if not flag:
                break
    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)


Fixed submission:
N = int(input())
xy = []
A = []
for i in range(N):
    Ai = int(input())
    xyi = []
    for j in range(Ai):
        xyi.append(list(map(int, input().split())))
    A.append(Ai)
    xy.append(xyi)

ans = 0

for i in range(2**N):
    bin_i = format(i, '0' + str(N) + 'b')
    flag = True
    for j in range(N):
        for k in range(A[j]):
            if bin_i[j] == '1' and xy[j][k][1] != int(bin_i[xy[j][k][0]-1]):
                flag = False
                break
        if not flag:
            break

    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())

# 暗証番号は 000-999 の最大1000種類

ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    # print(v)
    n = 0
    f = [False] * N
    for j in range(len(S)):
        if v[n] == S[j]:
            n += 1
        if n >= 3:
            # print(v)
            ans += 1
            break

print(ans)


Fixed submission:
N = int(input())
S = list(input())

# 暗証番号は 000-999 の最大1000種類

ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    # print(v)
    n = 0
    f = [False] * N
    for j in range(len(S)):
        if v[n] == S[j]:
            n += 1
        if n >= 3:
            # print(v)
            ans += 1
            break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(M):
    A.sort(reverse=True)
    A[0] //= 2

print(sum(A))


Fixed submission:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

N, M = map(int, input().split())
A = []
for i in input().split():
    heappush(A, -1 * int(i))
# print(A)

for _ in range(M):
    val = heappop(A)
    if val == 0:
        break
    heappush(A, (val+1)//2)

print(-1 * sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(M):
    A.sort(reverse=True)
    A[0] //= 2

print(sum(A))


Fixed submission:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

N, M = map(int, input().split())
A = []
for i in input().split():
    heappush(A, -1 * int(i))
# print(A)

for _ in range(M):
    val = heappop(A)
    if val == 0:
        break
    heappush(A, (val+1)//2)

print(-1 * sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

# print(A * K)

ans = 0
meets = [0] * N
for i in range(N):
    for j in range(N):
        ans += int(i < j and A[i] > A[j])
        meets[i] += int(A[i] > A[j])
ans *= K
# print(meets)

ans += sum(meets) * K * (K - 1) // 2

print(ans % MOD)


Fixed submission:
import itertools

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

# print(A * K)

ans = 0
meets = [0] * N
for i in range(N):
    for j in range(N):
        ans += int(i < j and A[i] > A[j])
        meets[i] += int(A[i] > A[j])
ans *= K
# print(meets)

ans += sum(meets) * K * (K - 1) // 2

print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())

def generate_prime_numbers():
    search_range = 150
    search_list = [True for i in range(0, search_range+1)]
    search_list[0] = False
    search_list[1] = False
    search_list[2] = True
    for i in range(2, search_range+1):
        for j in range(i*2, search_range+1, i):
            search_list[j] = False
    prime_numbers = [i for i in range(search_range+1) if search_list[i] == True]
    return prime_numbers[:27]

prime_numbers = generate_prime_numbers()
encoded_strings = []
for i in range(N):
    S = input()
    encoded_string = 1
    for c in S:
        char_to_int = ord(c) - ord('a')
        encoded_string *= prime_numbers[char_to_int]
    encoded_strings.append(encoded_string)
# print(encoded_strings)

ans = 0
for comb in itertools.combinations(encoded_strings, 2):
    if comb[0] == comb[1]:
        ans += 1

print(ans)


Fixed submission:
import itertools
from collections import Counter
import math

N = int(input())

def generate_prime_numbers():
    search_range = 150
    search_list = [True for i in range(0, search_range+1)]
    search_list[0] = False
    search_list[1] = False
    search_list[2] = True
    for i in range(2, search_range+1):
        for j in range(i*2, search_range+1, i):
            search_list[j] = False
    prime_numbers = [i for i in range(search_range+1) if search_list[i] == True]
    return prime_numbers[:27]

def combination(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

prime_numbers = generate_prime_numbers()
encoded_strings = []
for i in range(N):
    S = input()
    encoded_string = 1
    for c in S:
        char_to_int = ord(c) - ord('a')
        encoded_string *= prime_numbers[char_to_int]
    encoded_strings.append(encoded_string)
# print(encoded_strings)

ans = 0
# for comb in itertools.combinations(encoded_strings, 2):
#     if comb[0] == comb[1]:
#         ans += 1
counter = Counter(encoded_strings)
for i in counter.values():
    if i > 1:
        ans += combination(i, 2)

print(ans)