Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce


def gcd(numbers):
    return reduce(fractions.gcd, numbers)


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(A[:i]+A[i+1:]))
    print(ans)


if __name__ == '__main__':
    solve()

Fixed submission:
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    left = [0 for _ in range(N+1)]
    right = [0 for _ in range(N+1)]
    for i in range(N):
        left[i+1] = gcd(left[i], A[i])
    for i in range(N-1, -1, -1):
        right[i] = gcd(right[i+1], A[i])
    for i in range(N):
        ans = max(ans, gcd(left[i], right[i+1]))
    print(ans)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce


def gcd(numbers):
    return reduce(fractions.gcd, numbers)


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(A[:i]+A[i+1:]))
    print(ans)


if __name__ == '__main__':
    solve()

Fixed submission:
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    left = [0 for _ in range(N+1)]
    right = [0 for _ in range(N+1)]
    for i in range(N):
        left[i+1] = gcd(left[i], A[i])
    for i in range(N-1, -1, -1):
        right[i] = gcd(right[i+1], A[i])
    for i in range(N):
        ans = max(ans, gcd(left[i], right[i+1]))
    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, Q = map(int, input().split())
    S = input()
    l = [0 for _ in range(Q)]
    r = l[:]
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    
    ac_head = []
    for i, char in enumerate(S[:-1]):
        if char == 'A' and S[i+1] == 'C':
            ac_head.append(i)
    
    for i in range(Q):
        cnt = 0
        for index in ac_head:
            if l[i] - 1 <= index <= r[i] - 2:
                cnt += 1
            elif r[i] - 2 < index:
                break
        print(cnt)


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N, Q = map(int, input().split())
    S = input()
    l = [0 for _ in range(Q)]
    r = l[:]
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    
    ac_head = [0 for _ in range(N+1)]
    for i, char in enumerate(S[:-1]):
        if char == 'A' and S[i+1] == 'C':
            ac_head[i+1] = 1 + ac_head[i]
        else:
            ac_head[i+1] = ac_head[i]
    
    for a, b in zip(l, r):
        print(ac_head[b-1] - ac_head[a-1])


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, Q = map(int, input().split())
    S = input()
    l = [0 for _ in range(Q)]
    r = l[:]
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    
    ac_head = []
    for i, char in enumerate(S[:-1]):
        if char == 'A' and S[i+1] == 'C':
            ac_head.append(i)
    
    for i in range(Q):
        cnt = 0
        for index in ac_head:
            if l[i] - 1 <= index <= r[i] - 2:
                cnt += 1
            elif r[i] - 2 < index:
                break
        print(cnt)


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N, Q = map(int, input().split())
    S = input()
    l = [0 for _ in range(Q)]
    r = l[:]
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    
    ac_head = [0 for _ in range(N+1)]
    for i, char in enumerate(S[:-1]):
        if char == 'A' and S[i+1] == 'C':
            ac_head[i+1] = 1 + ac_head[i]
        else:
            ac_head[i+1] = ac_head[i]
    
    for a, b in zip(l, r):
        print(ac_head[b-1] - ac_head[a-1])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

dp = [-1] * (10 ** 5 + 1)


def dfs(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


def solve():
    ans = 0
    for v in range(1, N+1):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

dp = [-1] * (10 ** 5 + 1)


def dfs(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for child in graph[v]:
        res = max(res, dfs(child) + 1)
    dp[v] = res
    return res


def solve():
    ans = 0
    for v in range(1, N + 1):
        ans = max(ans, dfs(v))
    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    counter = defaultdict(int)
    for ai in A:
        counter[ai] += 1
    
    sorted_c = sorted(counter.values())
    ans = 0
    for i in range(len(counter) - K):
        ans += sorted_c[i]
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    ans = 10 ** 9
    for i in range(N):
        cnt = 0
        ai = A[i]
        while 1:
            if ai % 2 == 0:
                ai //= 2
                cnt += 1
            else:
                break
        ans = min(ans, cnt)
    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_right


def solve():
    N, *ABC = map(int, open(0).read().split())
    A = ABC[:N]
    B = ABC[N:2*N]
    C = ABC[2*N:]
    B.sort()
    C.sort()
    
    ans = 0
    for i in range(N):
        index = bisect_right(B, A[i])
        for j in range(index, N):
            ans += N - bisect_right(C, B[j])
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
from bisect import bisect_left, bisect_right


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A.sort()
    C.sort()
    
    ans = 0
    for i in range(N):
        cnt_a = bisect_left(A, B[i])
        cnt_b = N - bisect_right(C, B[i])
        ans += cnt_a * cnt_b
    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if B[i][j] == B[i][k] + B[k][j]:
                    A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()


Fixed submission:
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A))
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if B[i][j] == B[i][k] + B[k][j]:
                    A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()


Fixed submission:
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
rline = sys.stdin.readline

N = int(rline())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, rline().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
to_k = [0] * N


def dfs(node, parent, dist):
    to_k[node] = dist
    
    for child, d in graph[node]:
        if child != parent:
            dfs(child, node, dist + d)


def solve():
    Q, K = map(int, rline().split())
    K -= 1
    dfs(K, -1, 0)
    for _ in range(Q):
        x, y = map(lambda z: int(z) - 1, rline().split())
        print(to_k[x] + to_k[y])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
rline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(rline())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, rline().split())
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])
to_k = [0] * N


def dfs(node, parent, dist):
    to_k[node] = dist
    
    for child, d in graph[node]:
        if child != parent:
            dfs(child, node, dist + d)


def solve():
    Q, K = map(int, rline().split())
    K -= 1
    dfs(K, -1, 0)
    for _ in range(Q):
        x, y = map(lambda z: int(z) - 1, rline().split())
        print(to_k[x] + to_k[y])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    fen_dist, sun_dist = [0] * N, [0] * N
    
    def dfs1(node, parent, dist):
        fen_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs1(child, node, dist + 1)
    
    def dfs2(node, parent, dist):
        sun_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs2(child, node, dist + 1)
    
    dfs1(0, -1, 0)
    dfs2(N - 1, -1, 0)
    
    cnt_fen, cnt_sun = 0, 0
    for i in range(N):
        if fen_dist[i] <= sun_dist[i]:
            cnt_fen += 1
        else:
            cnt_sun += 1
    
    if cnt_fen < cnt_sun:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    fen_dist, sun_dist = [0] * N, [0] * N
    
    def dfs1(node, parent, dist):
        fen_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs1(child, node, dist + 1)
    
    def dfs2(node, parent, dist):
        sun_dist[node] = dist
        for child in graph[node]:
            if child != parent:
                dfs2(child, node, dist + 1)
    
    dfs1(0, -1, 0)
    dfs2(N - 1, -1, 0)
    
    cnt_fen, cnt_sun = 0, 0
    for i in range(N):
        if fen_dist[i] <= sun_dist[i]:
            cnt_fen += 1
        else:
            cnt_sun += 1
    
    if cnt_fen <= cnt_sun:
        print('Snuke')
    else:
        print('Fennec')


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    _ = int(input())
    a = list(map(int, input().split()))
    
    counter = [0] * 9
    for ai in a:
        counter[ai // 400] += 1
    
    ans_min = 0
    for i in range(8):
        if 0 < counter[i]:
            ans_min += 1
    
    ans_max = min(8, ans_min + counter[-1])
    print(ans_min, ans_max)


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    _ = int(input())
    a = list(map(int, input().split()))
    
    counter = [0] * 9
    for ai in a:
        counter[min(8, ai // 400)] += 1
    
    ans_min = 0
    for i in range(8):
        if 0 < counter[i]:
            ans_min += 1
    
    ans_max = ans_min + counter[-1]
    if ans_min == 0:
        ans_min = 1
    print(ans_min, ans_max)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
n = input()
m = input()
lst = []
if m in n:
    print(0)
else:
    for i in range(len(n) - len(m)):
        count = 0
        for j in range(i, len(m) + i):
            if n[j] != m[j-i]:
                count += 1
        lst.append(count)
    print(min(lst))

Fixed submission:
n = input()
m = input()
lst = []
if m in n:
    print(0)
else:
    for i in range(len(n) - len(m) + 1):
        count = 0
        for j in range(i, len(m) + i):
            if n[j] != m[j-i]:
                count += 1
        lst.append(count)
    print(min(lst))
Buggy python submission (verdict: Runtime Error):
n = input()
summ = 0
lst = list(map(int, input().split()))
for i in range(len(lst) - 1):
    if lst[i] > lst[i + 1]:
        k = lst[i] - lst[i + 1]
        lst.replace(lst[i + 1], lst[i + 1] + k)
        summ += k
print(summ)

Fixed submission:
n = input()
summ = 0
lst = list(map(int, input().split()))
for i in range(len(lst) - 1):
    if lst[i] > lst[i + 1]:
        k = lst[i] - lst[i + 1]
        lst[i + 1] = lst[i + 1] + k
        summ += k
print(summ)
Buggy python submission (verdict: Runtime Error):
k=int(input())

print('ACL'*K)

Fixed submission:
k=int(input())
print('ACL'*k)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

l = [None] * N

for i in range(N):
    l[i] = list(map(int, input().split()))

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

print(max([d(p0,p1) for p0 in l for p1 in l]))




Fixed submission:
N = int(input())

l = [None] * N

for i in range(N):
    l[i] = list(map(int, input().split()))

minX = min([e[0] for e in l])
minY = min([e[1] for e in l])
maxX = max([e[0] for e in l])
maxY = max([e[1] for e in l])

def d(_a, _b):
    return abs(_a[0]-_b[0])+abs(_a[1]-_b[1])

s0 = min([d([minX,minY], e) for e in l])
s1 = min([d([maxX,maxY], e) for e in l])
 
t0 = min([d([maxX,minY], e) for e in l])
t1 = min([d([minX,maxY], e) for e in l])
 

print(d([minX,minY], [maxX,maxY]) - min(s0+s1, t0+t1))
Buggy python submission (verdict: Runtime Error):

d,t,s = map(int, input().split())
print('Yes' if d <= t*s else 'No")


  
  


Fixed submission:
d,t,s = map(int, input().split())
print('Yes' if d <= t*s else 'No')
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()

def d(s,t):
  return sum([1 if i!=j else 0 for i,j in zip(s,t)])

print(min([d(S[i:], T) for i in range(len(S)-len(T))]))


Fixed submission:
S = input()
T = input()

def d(s,t):
  return sum([1 if i!=j else 0 for i,j in zip(s,t)])

print(min([d(S[i:], T) for i in range(len(S)-len(T) + 1)]))
Buggy python submission (verdict: Runtime Error):
N == int(input())
count = 0
for i in range(N-1):
  s = list(map(int, input().split()))
  if s[0] == s[1]:
    count += 1
if count >= 3:
  print("Yes")
else:
  print("No")

Fixed submission:
N = int(input())
c = 0
for i in range(N):
  a, b = map(int, input().split())
  if a == b:
    c += 1
  else:
    c =0
  if c == 3:
    break
if c == 3:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
N  =int(input())
c = 0
for i in range(N):
  c += N-1//i+1
print(c)  
  


Fixed submission:
N  =int(input())
c = 0
for i in range(N):
  c += (N-1)//(i+1)
print(c)

Buggy python submission (verdict: Runtime Error):
N  =int(input())
c = 0
for i in range(N):
  c += n-1//i+1
print(c)  
  


Fixed submission:
N  =int(input())
c = 0
for i in range(N):
  c += (N-1)//(i+1)
print(c)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
c = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if (i+1)*(j+1)+(k+1)==N:
        c += 1
print(c)      

Fixed submission:
N  =int(input())
c = 0
for i in range(N):
  c += (N-1)//(i+1)
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = 10**9+7
for i in range(n):
  for j in range(i+1,n):
    ans += (a[i]*a[j])%mod
    
print(ans%mod)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
arr = [0]*(n+1)
ans = 0
mod = 10**9+7
for i in range(n):
  arr[i+1] += arr[i]+a[i]
  
for i in range(n):
  ans += (a[i]*(arr[n]-arr[i+1]))%mod
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
X,K,D = map(int,input().split())

X = abs(X)

if X-K*D <= 0:
    d = X//D
    K -= d
    x -= D*d
    if K%2 == 0:
        print(a)
    else:
        print(abs(a-d))
else:
    print(X-K*D)

Fixed submission:
X,K,D = map(int,input().split())

X = abs(X)

if X-K*D <= 0:
    d = X//D
    if (K-d%2)%2:
        print(D-X%D)
    else:
        print(X%D)
else:
    print(X-K*D)
Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
item = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r][c] = v


dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]

for i in range(R+1):
    for j in range(C+1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の"行"に移動する場合（下に移動するので今まで獲得したアイテムの個数はリセットされる）
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i+1][j] = max(dp[0][i+1][j], here)
                # 移動先のアイテムをとる場合
                dp[1][i+1][j] = max(dp[1][i+1][j], here+item[i+1][j])
            # 次の列に移動する場合（右に移動するのでその行で獲得したアイテムの個数は維持される）
            if j + 1 <= C:
                dp[k][i][j+1] = max(dp[k][i][j+1], here)
                # 現在のkが3未満のときのみ，移動先のアイテムをとることが可能
                if k < 3:
                    dp[k+1][i][j+1] = max(dp[k+1][i][j+1], here+item[i][j+1])

ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
item = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    item[r][c] = v


dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]

for i in range(R+1):
    for j in range(C+1):
        for k in range(4):
            here = dp[k][i][j]
            # 次の"行"に移動する場合（下に移動するので今まで獲得したアイテムの個数はリセットされる）
            if i + 1 <= R:
                # 移動先のアイテムを取らない場合
                dp[0][i+1][j] = max(dp[0][i+1][j], here)
                # 移動先のアイテムをとる場合
                dp[1][i+1][j] = max(dp[1][i+1][j], here+item[i+1][j])
            # 次の列に移動する場合（右に移動するのでその行で獲得したアイテムの個数は維持される）
            if j + 1 <= C:
                dp[k][i][j+1] = max(dp[k][i][j+1], here)
                # 現在のkが3未満のときのみ，移動先のアイテムをとることが可能
                if k < 3:
                    dp[k+1][i][j+1] = max(dp[k+1][i][j+1], here+item[i][j+1])

ans = 0
for k in range(4):
    ans = max(ans, dp[k][-1][-1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
A = list(map(int,input().split()))

prev = 1
for i in range(k):
  prev *= A[k-i-1]
 
left = 0
right = k
tmp = prev
while right<n:
  tmp /= A[left]
  tmp *= A[right]
  if tmp>prev:
    print("Yes")
  else:
    print("No")
  prev = tmp
  left += 1
  right += 1

Fixed submission:
n,k = map(int,input().split())
A = list(map(int,input().split()))
left = 0
right = k
while right<n:
  if A[right]>A[left]:
    print("Yes")
  else:
    print("No")
  left += 1
  right += 1
Buggy python submission (verdict: Runtime Error):
a = int(input)

ans = a + a**2 + a**3

print(ans)

Fixed submission:
a = int(input())

ans = a + a**2 + a**3

print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()
cnt = 0
for i in len(s):
  if s[i] != t[i]:
    cnt += 1
    
print(cnt)

Fixed submission:
s = input()
t = input()
cnt = 0
for i in range(len(s)):
  if s[i] != t[i]:
    cnt += 1
    
print(cnt)
Buggy python submission (verdict: Runtime Error):
x = list(map(int,input().split()))

print(x.index("0")+1)

Fixed submission:
x = list(map(int,input().split()))
 
print(x.index(0)+1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = sorted(list(map(int,input().split())))
arr = [0]*(max(a)+1)

for i in a:
  arr[i]+=1
  tmp = i
  if arr[i]<=1:
      while (tmp+i)<=max(a):
        tmp += i
        if arr[tmp] !=0:
          arr[tmp] =2
        else:
          arr[tmp] +=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)
      

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
arr = [0]*(max(a)+1)

for i in a:
  arr[i]+=1
  tmp = i
  while (tmp+i)<=max(a):
    tmp += i
    if arr[tmp] !=0:
      arr[tmp] =2
    else:
      arr[tmp] +=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)
      
  

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)

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

flag = [True]*n
for i in range(n):
  for j in range(i+1,n):
    if flag[i] == True and flag[j] == True:
      if A[i]%A[j] == 0:
        flag[i] = False
      if A[j]%A[i] == 0:
        flag[j] = False
print(flag.count(True))

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
import math

a,b = map(float,input().split())
ans = math.floor(a*b)
print(ans)

Fixed submission:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def inc(n):
  ans = 0
  i = 1
  while True:
    if n - i >= 0:
      n -= i
      i += 1
      ans += 1
    else:
      break
  return ans

import collections

n = int(input())

c = collections.Counter(prime_factorize(n))

num = c.values()

ans = 0

for i in num:
  ans += inc(i)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,n = map(int,input().split())
sum = 0
ans = 0

for i in range(1,n+1):
   sum += (a*i)//b-a*(i//b)
   ans = max(sum,ans)
   sum = 0 
    
print(ans)

Fixed submission:
A, B, N = map(int, input().split())
ans = 0
x = min(B-1, N)
print((A*x)//B-A*(x//B))