Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())

sn = math.sqrt(N) // 1
a = 0

for i in range(1, sn + 1):
  if N % i == 0:
    a = i
    break

print(int(a + (N / a) - 2))

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)

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

N = int(input())

sn = math.sqrt(N) // 1
a = 0

for i in range(1, sn + 1):
  if N % i == 0:
    a = i
    break

print(int(i + (N / i) - 2))

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)

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

N = int(input())

sn = math.sqrt(N) // 1
i = 0

for i in range(1, sn + 1):
  if N % i == 0:
    break

print(int(i + (N / i) - 2))

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)

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

N = int(input())

sn = math.sqrt(N) // 1

while True:
  if N % sn == 0:
    break
  sn += 1

print(int(sn + (N / sn) - 2))

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)

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

sn = math.sqrt(N) // 1

while True:
  if N % sn == 0:
    break
  sn += 1

print(sn + (N / sn) - 2)

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)

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

sn = math.sqrt(N)

while True:
  if N % sn == 0:
    break
  sn += 1

print(sn + (N / sn) - 2)

Fixed submission:
import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
L = LI()

L.sort()

ans = 0
for i, l in enumerate(L):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if l + L[j] <= L[k]:
                break
            ans += 1

print(ans)

Fixed submission:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
L = LI()

L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        c = bisect.bisect_left(L, L[i]+L[j])

        ans += max(0, c - (j+1))

print(ans)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

print(((int((K*(K-1))//2)%MOD)*tmp+ans*K)%M)


Fixed submission:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
N, K = map(int, input().split())
# 横
A = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
tmp = 0

for i, a in enumerate(A) :
    for aa in range(i + 1, N) :
        if a > A[aa] :
            ans += 1

for a in A :
    for aa in A :
        if a > aa :
            tmp += 1

print(((int((K*(K-1))//2)%MOD)*tmp+ans*K)%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [collections.Counter(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
for i, s in enumerate(S) :
    for ss in range(i + 1, N) :
        if s == S[ss] :
            ans += 1

print(ans)


Fixed submission:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [''.join(sorted(input())) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
dic = {}
for s in S :
    if not s in dic :
        dic[s] = 0
    
    ans += dic[s]
    dic[s] += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [sorted(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
for i, s in enumerate(S) :
    for ss in range(i + 1, N) :
        if s == S[ss] :
            ans += 1

print(ans)


Fixed submission:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

N = int(input())
# S = input()
# N, M = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
S = [''.join(sorted(input())) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]

ans = 0
dic = {}
for s in S :
    if not s in dic :
        dic[s] = 0
    
    ans += dic[s]
    dic[s] += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
L, R = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]
ans = 3000

for i in range(L,R+1):
        for j in range(L,R+1):
            if i<j:
                ans=min(ans,(i*j)%2019)
                
print(ans)



Fixed submission:
# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
L, R = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]
ans = 3000

if R - L + 1 > 2019 :
    print(0)
else :
    for i in range(L,R+1):
            for j in range(L,R+1):
                if i<j:
                    ans=min(ans,(i*j)%2019)
                
    print(ans)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

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

# N = int(input())
# L = [int(x) for x in input().split()]
A, B, C, D = map(int, input().split())
# S = input()

def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def kosu(n, p):
    return n // p

x = kosu(B, C) - kosu(A - 1, C)
y = kosu(B, D) - kosu(A - 1, D)
z = kosu(B, lcm(C, D)) - kosu(A - 1, lcm(C, D))

print((B - A + 1) - (x + y - z))


Fixed submission:
# coding: utf-8

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

# N = int(input())
# L = [int(x) for x in input().split()]
A, B, C, D = map(int, input().split())
# S = input()

def gcd(x, y):
    if x % y == 0:
        return y
        
    return gcd(y, x % y)


def lcm(x, y):
    return (x * y) // gcd(x, y)


def kosu(n, p):
    return n // p

x = kosu(B, C) - kosu(A - 1, C)
y = kosu(B, D) - kosu(A - 1, D)
z = kosu(B, lcm(C, D)) - kosu(A - 1, lcm(C, D))

print((B - A + 1) - (x + y - z))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

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

N = int(input())
# L = [int(x) for x in input().split()]
# N, M = map(int, input().split())
# S = input()

ball = [[int(x) for x in input().split()] for _ in range(N)]
dist = {}

for i, a in enumerate(ball):
    x0 = a[0]
    y0 = a[1]

    for j, b in enumerate(ball):
        x1 = b[0]
        y1 = b[1]

        xy = (x1-x0, y1-y0)

        if xy == (0, 0):
            continue

        if not xy in dist:
            dist[xy] = 1
        else:
            dist[xy] += 1
            
print(N - max(dist.values()))


Fixed submission:
# coding: utf-8

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

N = int(input())
# L = [int(x) for x in input().split()]
# N, M = map(int, input().split())
# S = input()

ball = [[int(x) for x in input().split()] for _ in range(N)]
dist = {}

for i, a in enumerate(ball):
    x0 = a[0]
    y0 = a[1]

    for j, b in enumerate(ball):
        x1 = b[0]
        y1 = b[1]

        xy = (x1-x0, y1-y0)

        if xy == (0, 0):
            continue

        if not xy in dist:
            dist[xy] = 1
        else:
            dist[xy] += 1

try:
    num = max(dist.values())
except:
    num = 0

print(N - num)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

dp = [0] * (N+10)
dp[0] = 1

for i in range(N):
    if i in A:
        continue

    dp[i+1] = ((dp[i] % MOD) + (dp[i+1] % MOD)) % MOD
    dp[i+2] = ((dp[i] % MOD) + (dp[i+2] % MOD)) % MOD

print(dp[N])


Fixed submission:
# coding: utf-8

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

MOD = 10**9 + 7
# N = int(input())
# L = [int(x) for x in input().split()]
N, M = map(int, input().split())
# S = input()

dp = [0] * (N + 5)
dp[0] = 1

for _ in range(M):
    dp[int(input())] = -1

for i in range(N):
    if dp[i] == -1:
        continue
    if dp[i + 1] != -1:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
    if dp[i + 2] != -1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N, M = LI()
A = RI(M)

dp = [0] * (N+10)
dp[0] = 1

for i in range(N):
    if i in A:
        continue

    dp[i+1] = (dp[i] + dp[i+1]) % MOD
    dp[i+2] = (dp[i] + dp[i+2]) % MOD

print(dp[N])


Fixed submission:
# coding: utf-8

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

MOD = 10**9 + 7
# N = int(input())
# L = [int(x) for x in input().split()]
N, M = map(int, input().split())
# S = input()

dp = [0] * (N + 5)
dp[0] = 1

for _ in range(M):
    dp[int(input())] = -1

for i in range(N):
    if dp[i] == -1:
        continue
    if dp[i + 1] != -1:
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
    if dp[i + 2] != -1:
        dp[i + 2] += dp[i]
        dp[i + 2] %= MOD

print(dp[N])
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

import sys
import math
input = sys.stdin.readline

# N = int(input())
# L = [int(x) for x in input().split()]
N, K = map(int, input().split())
# S = input()

max_pow = int(math.log2(K) + 0.9)

one_half = [0] * (max_pow + 1)
one_half[0] = 1
for i in range(1, max_pow + 1) :
    one_half[i] = one_half[i - 1] * 0.5

ans = 0
for i in range(1, N + 1) :
    pow_num = math.ceil(math.log2(K / i))
    
    if pow_num <= 0 :
        ans += 1
    else :
        ans += one_half[pow_num]
        
print(ans / N)


Fixed submission:
# coding: utf-8

import sys
import math
input = sys.stdin.readline

# N = int(input())
# L = [int(x) for x in input().split()]
N, K = map(int, input().split())
# S = input()

max_pow = math.ceil(math.log2(K) + 0.9)

one_half = [0] * (max_pow + 1)
one_half[0] = 1
for i in range(1, max_pow + 1) :
    one_half[i] = one_half[i - 1] * 0.5

ans = 0
for i in range(1, N + 1) :
    pow_num = math.ceil(math.log2(K / i))
    
    if pow_num <= 0 :
        ans += 1
    else :
        ans += one_half[pow_num]

print(ans / N)
Buggy python submission (verdict: Runtime Error):
aa

Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

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

print(max(A + B, (max(A, B) + max(A - 1, B - 1))))

Buggy python submission (verdict: Runtime Error):
a

Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

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

print(max(A + B, (max(A, B) + max(A - 1, B - 1))))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

n, q = map(int, input().split())
s = input()

for _ in range(q):
    l, r = map(int, input().split())
    strs = s[l - 1 : r]
    
    print(strs.count("AC"))


Fixed submission:
N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

for k in AB:
    if M > k[1]:
        M -= k[1]
        ans += k[0] * k[1]
    else:
        ans += k[0] * M
        break

print(ans)



Fixed submission:
# coding: utf-8

# import sys
# input = sys.stdin.readline

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

k = 0
ans = 0
while M > 0:
    if M > AB[k][1]:
        M -= AB[k][1]
        ans += AB[k][0] * AB[k][1]
    else:
        ans += AB[k][0] * M
        break
    
    k += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

ans = 0
while M > 0:
    if AB[0][1] == 0:
        AB = AB[1:]

    ans += AB[0][0]
    M -= 1

    AB[0][1] -= 1

print(ans)



Fixed submission:
# coding: utf-8

# import sys
# input = sys.stdin.readline

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

k = 0
ans = 0
while M > 0:
    if M > AB[k][1]:
        M -= AB[k][1]
        ans += AB[k][0] * AB[k][1]
    else:
        ans += AB[k][0] * M
        break
    
    k += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import numpy as np

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

ans = 0
while M > 0:
    if AB[0][1] == 0:
        AB = AB[1:]

    ans += AB[0][0]
    M -= 1

    AB[0][1] -= 1

print(ans)


Fixed submission:
# coding: utf-8

# import sys
# input = sys.stdin.readline

N, M = map(int, input().split())

AB = [list(map(int, input().split())) for __ in range(N)]
AB.sort(key=lambda x : x[0])

k = 0
ans = 0
while M > 0:
    if M > AB[k][1]:
        M -= AB[k][1]
        ans += AB[k][0] * AB[k][1]
    else:
        ans += AB[k][0] * M
        break
    
    k += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()
n = len(s)
MOD = 10 ** 9 + 7

ans = 0
comb = 1
for i in range(k+1):
    if i > 0: comb = comb * (n+i-1) * pow(i, MOD-2, MOD) % MOD
    ans = (ans + comb * pow(25, i, MOD) * pow(26, k-i, MOD)) % MOD
print(ans)


Fixed submission:
k = int(input())
s = input()
n = len(s)
MOD = 10 ** 9 + 7

ans = 0
comb = 1
for i in range(k+1):
    if i > 0: comb = comb * (n+i-1) * pow(i, MOD-2, MOD) % MOD
    ans = (ans + comb * pow(25, i, MOD) * pow(26, k-i, MOD)) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)


Fixed submission:
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
def calc_factors(n):
    factors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            j = n // i
            if j != i: factors.append(j)
            factors.append(i)
    return factors

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        done[num] = 1
        continue

    factors = calc_factors(num)
    for f in factors:
        if done[f]:
            break
    else:
        ans += 1
        done[num] = 1

print(ans)


Fixed submission:
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
def calc_factors(n):
    factors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            j = n // i
            if j != i: factors.append(j)
            factors.append(i)
    return factors

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = set()
for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        done.add(num)
        continue
    factors = calc_factors(num)
    for f in factors:
        if f in done:
            break
    else:
        ans += 1
    done.add(num)
print(ans)


Fixed submission:
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

n = int(input())
a = sorted(map(int, input().split()))

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
t = input()
ans = ''
for i in range(len(t)):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)


Fixed submission:
t = input()
n = len(t)
ans = ''
for i in range(n):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
mods = [0] * 2019
mods[0] = 1

for i in range(n-1, -1, -1):
    mod = int(s[i:]) % 2019
    mods[mod] += 1

ans = 0
for i in range(2019):
    ans += mods[i] * (mods[i] - 1) // 2
print(ans)


Fixed submission:
s = input()
n = len(s)
MOD = 2019
mods = [0] * MOD
mods[0] = 1

prev = 0
for i in range(n-1, -1, -1):
    mod = int(s[i]) * pow(10, n-i, MOD) % MOD
    mod = (mod + prev) % MOD
    mods[mod] += 1
    prev = mod

ans = 0
for i in range(MOD):
    ans += mods[i] * (mods[i] - 1) // 2
print(ans)