Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Fixed submission:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())
X = sorted([list(map(int,input().split())) for i in range(n)])
mod = 998244353
e = [[] for i in range(n)]

def dfs(x):
    count = 1

    for i in e[x]:
        count *= dfs(i)
        count %= mod
    return count+1

q = deque([])

for i in range(n-1,-1,-1):
    a,b = X[i]
    while q and q[0][0] < a+b:
        e[i].append(q[0][1]) 
        q.popleft()
    q.appendleft([a,i])

ans = 1
for i,j in q:
    ans *= dfs(j)
    ans %= mod
print(ans)


Fixed submission:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
ans = [0]*n

for i in range(3):
    a,b = map(int,input().split())
    if a == 1 and b == 0:
        print(-1)
        exit()
    if ans[a-1] == 0:
        ans[a-1] = b
    else:
        if b != ans[a-1]:
            print(-1)
            exit()
if ans[0] == 0:
    ans[0] = 1
print(*ans,sep="")


Fixed submission:
n,m = map(int,input().split())
ans = [0]*n

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

for i in range(1000):
    if len(str(i)) == n:
        
        check = True
        for j,k in l:
            if int(str(i)[j-1]) != k:
                check = False
                
        if check:
            print(i)
            exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

n,m,k = map(int,input().split())
ans = [[0]*n for i in range(n)]

fre = [[] for i in range(n)]
blo = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    fre[a-1].append(b-1)
    fre[b-1].append(a-1)
for i in range(k):
    a,b = map(int,input().split())
    blo[a-1].append(b-1)
    blo[b-1].append(a-1)

group = [-1]*n
def check():
    
    count = 1
    for i in range(n):
        if group[i] == -1:
            dfs(i,count)
            count += 1
    return group

def dfs(i,count):
    q = deque([])
    q.append(i)
    while q:
        bef = q.pop()

        for nex in fre[bef]:
            if group[nex] == -1:
                group[nex] = count
                q.append(nex)
    
check()
for i in range(n):
    if group[i] == -1:
        print(0,end=" ")
    else:
        num = group.count(group[i])
        num -= len(fre[i])
        for j in blo[i]:
            if group[j] == group[i]:
                num -= 1
        print(num-1,end=" ")






Fixed submission:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

    n,m,k = map(int,input().split())

    fre = [[] for i in range(n)]

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

    group = [-1]*n
    def check():
        dic = {}
        count = 1
        for i in range(n):
            if group[i] == -1:
                a = dfs(i,count)
                dic[count] = a
                count += 1
        return group,dic

    def dfs(i,count):
        num = 0
        group[i] = count
        q = deque([])
        q.append(i)
        while q:
            bef = q.pop()

            for nex in fre[bef]:
                if group[nex] == -1:
                    group[nex] = count
                    q.append(nex)
                    num += 1
        return num
    group,dic = check()
    ans = []
    for i in range(n):
        a = group[i]
        ans.append([dic[a]-len(fre[i]),a])
    for i in range(k):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        if ans[a][1] == ans[b][1]:
            ans[a][0] -= 1
            ans[b][0] -= 1
    for i,j in ans:
        print(i,end=" ")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
l = list(map(int,input().split()))
x = 0
a = 0
for i in range(n-3):
    b = l[i]+l[i+1]+l[i+2]+l[i+3]
    if b > a:
        a = b
        x = i

def kitai(x):
    ans = 0
    for i in range(1,x+1):
        ans += i
    return ans/x
ans = 0
for i in range(x,x+m):
    ans += kitai(l[i])
print(ans)


Fixed submission:
n,m = map(int,input().split())
l = list(map(int,input().split()))

ans = 0
for i in range(m):
    ans += l[i]
a = ans
for i in range(m,n):
    a = a+l[i]-l[i-m]
    if a > ans:
        ans = a
print((ans+m)/2)
Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

count = 0
for i in range(1,len(str(n))):
    if i >= k:
        count += 9*comb(i-1,k-1)*(9**(k-1))
        

if k == 1:
    count += int(str(n)[0])
    print(count)
    exit()
if k == 2:
    count += (int(str(n)[0])-1)*9*(len(str(n))-1)
    
    count2 = 0
    for i in range(1,len(str(n))-1):
        if i >= 1:
            count2 += 9*comb(i-1,0)*(9**(0))
    count += int(str(n)[1])    
    print(count+count2)
    exit()

if k == 3:
    count += (int(str(n)[0])-1)*comb(len(str(n))-1,2)*81
    for i in range(1,len(str(n))-1):
        if i >= 2:
            count += 9*comb(i-1,2-1)*(9**(2-1))
    count += (int(str(n)[1])-1)*9*(len(str(n))-2)
    
    count2 = 0
    for i in range(1,len(str(n))-2):
        if i >= 1:
            count2 += 9*comb(i-1,0)*(9**(0))
    count += int(str(n)[2])    
    print(count+count2)
    exit()
        


    

Fixed submission:
n = int(input())
k = int(input())

dp = [[[0]*(2) for i in range(k+1)] for j in range(len(str(n))+1)]

dp[0][0][0] = 1

for i in range(len(str(n))):
    for j in range(k+1):
        for m in range(2):
            nd = int(str(n)[i])
            for l in range(10):
                ni = i+1
                nj = j
                nm = m
                if l != 0:
                    nj += 1
                if nj > k:
                    continue
                if nm == 0:
                    if  l > nd:
                        continue
                    elif l < nd:
                        nm = 1
                dp[ni][nj][nm] += dp[i][j][m]
print(dp[len(str(n))][k][0]+dp[len(str(n))][k][1])
Buggy python submission (verdict: Runtime Error):
def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,2*10**6+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      if (r < 0) or (n < r):
          return 0
      r = min(r, n - r)
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

if __name__ == "__main__":
  main()

Fixed submission:
def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,r2+c2+3):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,2*10**6+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      if (r < 0) or (n < r):
          return 0
      r = min(r, n - r)
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

if __name__ == "__main__":
  main()

Fixed submission:
def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,r2+c2+3):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

if __name__ == "__main__":
  main()
Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
dp = [float("inf")]*(h+10001)
dp[0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[j] = min(dp[j],dp[j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[i])

print(ans)


Fixed submission:
h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)


Fixed submission:
h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)

Buggy python submission (verdict: Runtime Error):
h,n = map(int,input().split())
a = []
b = []
for i in range(n):
    x,y= map(int,input().split())
    a.append(x)
    b.append(y)
dp = [[float("inf")]*(h+3) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    for j in range(h+3):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
ans = float("inf")
for i in range(h,h+3):
    ans = min(ans,dp[n][i])

print(ans)

Fixed submission:
h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
count = 0
for i in range(1,n+1):
        for j in range(1,n+1):
            if i % 10 == int(str(j)[0]) and j % 10 == int(str(i)[0]):
                count += 1

print(count)

Fixed submission:
n = int(input())
count = 0
l = [[0]*10 for i in range(10)]
for i in range(1,n+1):
    l[int(str(i)[0])][int(str(i)[-1])] += 1
for i in range(1,10):
    for j in range(1,10):
        count += l[i][j]*l[j][i]
            

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b/fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


Fixed submission:
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    
print(a%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
ans = l[0]*l[1]/fractions.gcd(l[0],l[1])
for i in range(2,n):
    ans = ans*l[i]/fractions.gcd(ans,l[i])

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


Fixed submission:
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    
print(a%mod)

Buggy python submission (verdict: Runtime Error):
import fractions
n = int(input())
l = list(map(int,input().split()))

ans = l[0]*l[1]/fractions.gcd(l[0],l[1])
for i in range(2,n):
    ans = ans*l[i]/fractions.gcd(ans,l[i])

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))


Fixed submission:
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

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



for i in range(n):
    left.append((l[i][0]-l[i][1],l[i][0]+l[i][1]))
left.sort()   
count = 1
right = 10**10
for i in range(n):
    right = min(right,left[i][1])

while True:
    right2 = 10**10
    for i in range(n):
        if left[i][0] >= right:
            
            right2 = min(right2,left[i][1])
            
            
    if right2 == 10**10:
        print(count)
        exit()
    else:
        right = right2
        count += 1


Fixed submission:
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
left = []



for i in range(n):
    left.append((l[i][0]+l[i][1],l[i][0]-l[i][1]))
left.sort()   
count = 1
right = 10**10
right = left[0][0]
c = 0

while True:
    
    for i in range(c,n+1):
        if i == n:
            print(count)
            exit()
        if left[i][1] >= right:
            count += 1
            right = left[i][0]
            c = i
            
            
            
    if c == n-1:
        print(count)
        exit()
Buggy python submission (verdict: Runtime Error):
from collections import deque
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)
print(l[0][1])
ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

                for t in range(4):
                    nx = x+dx[t]
                    ny = y + dy[t]

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "#":
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)


Fixed submission:
from collections import deque
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)

ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

                for t in range(4):
                    nx = x+dx[t]
                    ny = y + dy[t]

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "#":
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = list(map(int,input().split()))
sa = []
for i in range(n-1):
    sa.append(l[i+1]-l[i])

mod = 10**9+7
ans = 0
count = 0
kai = 1
for i in range(n-1):
    kai *= (i+1)
    
for i in range(n-1):
    count += 1/(i+1)
    
    
    ans += sa[i]*count
    ans %= mod
    

print(int(kai*ans%mod))


Fixed submission:
n = int(input())
l = list(map(int,input().split()))
sa = []
for i in range(n-1):
    sa.append(l[i+1]-l[i])

mod = 10**9+7
ans = 0
count = 0
kai = 1
for i in range(1,n):
    kai *= i
    kai %= mod
    
for i in range(n-1):
    count += pow((i+1),mod-2,mod)
    
    ans += sa[i]*count
    ans %= mod


print(int(kai*ans%mod))

Buggy python submission (verdict: Runtime Error):
n = int(input())
l = list(map(int,input().split()))
sa = []
for i in range(n-1):
    sa.append(l[i+1]-l[i])

mod = 10**9+7
ans = 0
count = 0
kai = 1
for i in range(n-1):
    count += 1/(i+1)
    kai *= (i+1)
    
    ans += sa[i]*count
    ans %= mod

print(int(kai*ans%mod))


Fixed submission:
n = int(input())
l = list(map(int,input().split()))
sa = []
for i in range(n-1):
    sa.append(l[i+1]-l[i])

mod = 10**9+7
ans = 0
count = 0
kai = 1
for i in range(1,n):
    kai *= i
    kai %= mod
    
for i in range(n-1):
    count += pow((i+1),mod-2,mod)
    
    ans += sa[i]*count
    ans %= mod


print(int(kai*ans%mod))
Buggy python submission (verdict: Runtime Error):
import itertools

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

l = [x+1 for x in range(n)]
ans = []
count = 0
for v in itertools.permutations(l):
    count += 1
    ans = list(v)
    if ans == a:
        a1 = count
    elif ans == b:
        b1 = count

print(abs(a1-b1))
        




Fixed submission:
import itertools

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

l = [x+1 for x in range(n)]
ans = []
count = 0
for v in itertools.permutations(l):
    count += 1
    ans = list(v)
    if ans == a:
        a1 = count
    if ans == b:
        b1 = count

print(abs(a1-b1))
Buggy python submission (verdict: Runtime Error):
n,m,k = map(int,input().split())

if k >= n:
    n1 = 0
    if k >= n+m:
        m1 = 0
    else:
        m1 = m+n-k
print("{} {}".format(n1,m1))


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

if k >= n+m:
    print("0 0")
elif n+m > k >=n:
    m -= (k-n)
    print("0 {}".format(m))
else:
    print("{} {}".format(n-k,m))

Buggy python submission (verdict: Runtime Error):
n,m,k = map(int,input().split())

if k >= n:
    n1 = 0
    if k >= n+m:
        m1 = 0
    else:
        m1 = m+n-k
print("{} {}".format(n1,m1))

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

if k >= n+m:
    print("0 0")
elif n+m > k >=n:
    m -= (k-n)
    print("0 {}".format(m))
else:
    print("{} {}".format(n-k,m))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
elif n == 10:
  print(1)
else:
  count = 0
  for i in range(10,n,10):
    
    
    while i % 5 == 0:
      count += 1
      i /= 5
   
  print(count)

Fixed submission:
n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
else:
  count = 0
  for i in range(30):
    sub = 10 * (5**i)
    count += n // sub
    
    if sub > n:
      break
      
  print(count)

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

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
elif n == 10:
  print(1)
else:
  count = 0
  for i in range(10,n,10):
    
    if i % 5 == 0:
      while i % 5 == 0:
        count += 1
        i //= 5
   
  print(count)
        
  

Fixed submission:
n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
else:
  count = 0
  for i in range(30):
    sub = 10 * (5**i)
    count += n // sub
    
    if sub > n:
      break
      
  print(count)
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
n = x//100 + 1
for i in range(n):
  for j in range(n):
     for k in range(n):
         for l in range(n):
             for m in range(n):
                 for o in range(n):
                    c = 100*i + 101*j + 102*k + 103*l + 104*m + 105*o
                    if c == x:
                      print(1)
                      exit()
print(0)      


Fixed submission:
x = int(input())
n = x//100 + 1
 
for i in range(n):
  for j in range(n):
     for k in range(n):
         for l in range(n):
             for m in range(n):
                 c = 100*i + 101*j + 102*k + 103*l + 104*m
                 if x >= c:
                    t = x-c
                
                    if t%105 == 0:
                        print(1)
                        exit()
                    
print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

n = int(input())
s = list(input())
l = list(itertools.combinations(s,3))
c = []
for i in l:
  if not i in c:
    c.append(i)

print(len(c))

Fixed submission:
n = int(input())
s = input()

count = 0

for i in range(1000):
  a = "{0:03d}".format(i)
  if a[0] in s:
    idx1 = s.index(a[0])
    s1 = s[idx1+1:]
    if a[1] in s1:
      idx2 = s1.index(a[1])
      s2 = s1[idx2+1:]
      if a[2] in s2:
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
l = list(map(int,input().split()))
mo = [0]
mod = [0]
for i in range(n):
    a = l[i]%k
    mo.append((a+mo[-1])%k)
    mod.append((mo[-1]-(i+1))%k)
dic = {0:1}
le = 1
ans = 0
for i in range(1,n+1):
    if le < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
        le += 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    print(dic)
print(ans)


Fixed submission:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mo = [0]
mod = [0]
for i in range(n):
    a = l[i]%k
    mo.append((a+mo[-1])%k)
    mod.append((mo[-1]-(i+1))%k)
dic = {0:1}
le = 1
ans = 0
for i in range(1,n+1):
    if le < k:
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
        le += 1
    else:
        dic[mod[i-k]] -= 1
        if mod[i] in dic:
            ans += dic[mod[i]]
            dic[mod[i]] += 1
        else:
            dic[mod[i]] = 1
    
print(ans)