Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

ans=-float('inf')
for i in range(n+1):
    tmp1=a[:n+i]
    tmp2=a[n+i:]
    tmp1.sort(reverse=True)
    tmp2.sort()
    ans=max(ans,sum(tmp1[:n])-sum(tmp2[:n]))
print(ans)

Fixed submission:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

left=[0]*(n+1)
right=[0]*(n+1)
left[0]=sum(a[:n])
right[n]=sum(a[n+n:])

mae,usi=a[:n],list(map(lambda x: x*-1,a[n+n:]))

heapq.heapify(mae)
heapq.heapify(usi)

for i in range(n):
    tmp=heapq.heappushpop(mae,a[n+i])
    left[i+1]=left[i]+a[n+i]-tmp
    tmp=heapq.heappushpop(usi,-a[n+n-i-1])
    right[n-i-1]=right[n-i]+a[n+n-i-1]+tmp
# print(mae)
# print(left)
# print(right)
ans=-float('inf')
for i in range(n+1):
    ans=max(ans, left[i]-right[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


s,t=input(),input()
q=int(input())
abcd=[list(map(int,input().split())) for i in range(q)]


for i in range(q):
    a,b,c,d=abcd[i]
    ss,tt=s[a-1:b],t[c-1:d]
    scnt=ss.count("A")-ss.count("B")
    tcnt=tt.count("A")-tt.count("B")
    if abs(scnt-tcnt)%3==0:
        print("YES")
    else:
        print("NO")

Fixed submission:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


s,t=input(),input()
q=int(input())
abcd=[list(map(int,input().split())) for i in range(q)]

scnt=[(0,0)]*(len(s)+1)
tcnt=[(0,0)]*(len(t)+1)
for i in range(len(s)):
    a,b=scnt[i]
    if s[i]=="A":
        a+=1
    else:
        b+=1
    scnt[i+1]=(a,b)
for i in range(len(t)):
    a,b=tcnt[i]
    if t[i]=="A":
        a+=1
    else:
        b+=1
    tcnt[i+1]=(a,b)
# print(scnt)
# print(tcnt)

for i in range(q):
    a,b,c,d=abcd[i]
    sa,sb=scnt[b],scnt[a-1]
    sa,sb=sa[0]-sb[0],sa[1]-sb[1]
    ta,tb=tcnt[d],tcnt[c-1]
    ta,tb=ta[0]-tb[0],ta[1]-tb[1]
    # print(sa,sb,ta,tb)

    if abs((sa-sb)-(ta-tb))%3==0:
        print("YES")
    else:
        print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
x=int(input())
import queue

q = queue.Queue()

q.put(0)
q.put("")
count=1
while 1:
    now=q.get()
    if now=="":
        count+=1
        q.put("")
        continue
    if now+count==x or now-count==x:
        print(count)
        break
    q.put(now+count)
    q.put(now)
    q.put(now-count)

Fixed submission:
x=int(input())
# import queue

# q = queue.Queue()

# q.put(0)
# q.put("")
i=0
now=0
while 1:
    i+=1
    now+=i
    if now>=x:
        print(i)
        break
Buggy python submission (verdict: Runtime Error):
import sys
import collections

import heapq
def input():
    return sys.stdin.readline()[:-1]

n=int(input())
a=list(map(int,input().split()))
tmp=collections.Counter(a)
b=list(tmp.values())
b=list(map(lambda  x:x*-1, b))
heapq.heapify(b)
ans=0
while 1:
    cnt1=heapq.heappop(b)
    if cnt1==-1:
        break
    cnt2=heapq.heappop(b)
    if cnt2==-1:
        ans+=cnt1*-2-2
        break
    ans+=max(cnt1,cnt2)*-2-2
    heapq.heappush(b,cnt1-max(cnt1,cnt2)-1)
    heapq.heappush(b,cnt2-max(cnt1,cnt2)-1)
print(n-ans)

Fixed submission:
import sys
import collections

import heapq
def input():
    return sys.stdin.readline()[:-1]

n=int(input())
a=list(map(int,input().split()))
tmp=collections.Counter(a)
if len(tmp)%2==0:
    print(len(tmp)-1)
else:
    print(len(tmp))
Buggy python submission (verdict: Time Limit Exceeded):
a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans+=1
print(ans)

Fixed submission:
a,b,x=map(int,input().split())
ans=0
ans+=b//x
ans-=(a-1)//x
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m=map(int,input().split())
kl=[list(map(int,input().split())) for i in range(n)]
uf=UnionFind(m)
for i in range(n):
    for j in range(2,kl[i][0]+1):    
        uf.union(kl[i][1], kl[i][j])

flag=uf.par[1]
for i in range(2,n):
    if flag!=uf.par[i]:
        print("NO")
        quit()
print("YES")

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    # 根ならその番号を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m=map(int,input().split())
kl=[list(map(int,input().split())) for i in range(n)]
uf=UnionFind(m)
for i in range(n):
    for j in range(2,kl[i][0]+1):    
        uf.union(kl[i][1], kl[i][j])

for i in range(1,n):
    if not uf.same_check(kl[0][1],kl[i][1]):
        print("NO")
        quit()
print("YES")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=(t+a)//wa
    while wa*j<t+a or t>j*ta[i+1][0] or a>j*ta[i+1][1]:
        j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=max((t+a+wa-1)//wa,(t+ta[i+1][0]-1)//ta[i+1][0],(a+ta[i+1][1]-1)//ta[i+1][1])
    # while wa*j<t+a or j*ta[i+1][0]<t or j*ta[i+1][1]<a:
    #     j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=1
    while wa*j<t+a or t>j*ta[i+1][0] or a>j*ta[i+1][1]:
        j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)

Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=max((t+a+wa-1)//wa,(t+ta[i+1][0]-1)//ta[i+1][0],(a+ta[i+1][1]-1)//ta[i+1][1])
    # while wa*j<t+a or j*ta[i+1][0]<t or j*ta[i+1][1]<a:
    #     j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)
Buggy python submission (verdict: Runtime Error):
n=input()
s=0
for i in range(n):
  s+=int(n[i])
if(s%9==0):
  print("Yes")
else:
  print("No")

Fixed submission:
n=input()
s=0
for i in range(len(n)):
  s+=int(n[i])
if(s%9==0):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
h,w,m=(int(i) for i in input().split())
l1=[]
l2=[0]*h
l3=[0]*w
for i in range(m):
    x,y=(int(i) for i in input().split())
    l1.append((x,y))
    l2[x-1]+=1
    l3[y-1]+=1
m1=max(l2)
m2=max(l3)
m3=max(m1,m2)
if(m3==m1):
    l4=[0]*w
    k=l2.index(m1)
    for i in range(m):
        if(l1[i][0]!=k+1):
           l4[l1[i][1]-1]+=1
    k1=max(l4)
    print(m1+k1)
else:
    l4=[0]*h
    k=l3.index(m2)
    for i in range(m):
        if(l1[i][0]!=k+1):
           l4[l1[i][1]-1]+=1
    k1=max(l4)
    k2=l4.index(k1)
    print(m2+k1)

Fixed submission:
h,w,m=(int(i) for i in input().split())
l1=[]
l2=[0]*h
l3=[0]*w
for i in range(m):
    x,y=(int(i) for i in input().split())
    l1.append((x,y))
    l2[x-1]+=1
    l3[y-1]+=1
m1=max(l2)
m2=max(l3)
m3=max(m1,m2)
if(m1>m2):
    l4=[0]*w
    k=l2.index(m1)
    for i in range(m):
        if(l1[i][0]!=k+1):
           l4[l1[i][1]-1]+=1
    k1=max(l4)
    print(m3+k1)
else:
    l4=[0]*h
    k=l3.index(m2)
    for i in range(m):
        if(l1[i][1]!=k+1):
           l4[l1[i][0]-1]+=1
    k1=max(l4)
    print(m3+k1)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
l1=[0]*(k-1)+[1]
for i in range(k):
    l1[k-1]*=l[i]
for i in range(k,n):
    l1+=[(l1[i-1]//l[i-k])*l[i]]
for i in range(k,n):
    if(l1[i]>l1[i-1]):
        print("Yes")
    else:
        print("No")

Fixed submission:
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
for i in range(k,n):
    if(l[i]>l[i-k]):
        print("Yes")
    else:
        print("No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
l1=[0]*(k-1)+[1]
for i in range(k):
    l1[k-1]*=l[i]
for i in range(k,n):
    l1+=[(l1[i-1]//l[i-k])*l[i]]
for i in range(k,n):
    if(l1[i]>l1[i-1]):
        print("Yes")
    else:
        print("No")

Fixed submission:
n,k=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
for i in range(k,n):
    if(l[i]>l[i-k]):
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
n=int(input())
if(n%1000==0):
  print(0)
else:
  print((math.ceil(n/1000)*1000)-n)

Fixed submission:
import math
n=int(input())
if(n%1000==0):
  print(0)
else:
  print((math.ceil(n/1000)*1000)-n)
Buggy python submission (verdict: Runtime Error):
n=int(input())
l=[int(i) for i in input().split()]
s=sum(l)
d={}
for i in range(n):
  if(l[i] in d):
    d[i]+=1
  else:
    d[i]=1
q=int(input())
for w in range(q):
  b,c=(int(i) for i in input().split())
  if(b in d):
    s-=((d[b]*b)+(d[b]*c))
    d[c]=d[b]
    d[b]=0
  print(s)

Fixed submission:
n=int(input())
l=[int(i) for i in input().split()]
s=sum(l)
d={}
for i in range(n):
  if(l[i] in d):
    d[l[i]]+=1
  else:
    d[l[i]]=1
q=int(input())
for w in range(q):
  b,c=(int(i) for i in input().split())
  if(b in d):
    s-=(d[b]*b)
    s+=(d[b]*c)
    if(c in d):
        d[c]+=d[b]
    else:
        d[c]=d[b]
    d[b]=0
  print(s)
Buggy python submission (verdict: Runtime Error):
n,k=(int(i) for i in input().split())
l=[i for i in range(1,n+1)]
for i in range(k):
  d=input()
  for i in input().split():
    l[i]=0
c=0
for i in l:
  if(i>0):
    c+=1
print(c)

Fixed submission:
n,k=(int(i) for i in input().split())
l=[1 for i in range(1,n+1)]
for i in range(k):
  d=input()
  l1=[int(j) for j in input().split()]
  for j in l1:
      l[j-1]=0
c=0
for i in l:
  if(i>0):
    c+=1
print(c)
Buggy python submission (verdict: Runtime Error):
n,m=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
if(sum(l)>=n):
	print(n-sum(l))
else:
	print(-1

Fixed submission:
n,m=(int(i) for i in input().split())
l=[int(i) for i in input().split()]
if(sum(l)<=n):
	print(n-sum(l))
else:
	print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[int(i) for i in input().split()]
c=0
for i in range(n):
  c1=min(l[:i+1])
  if(l[i]==c1):
    c+=1
print(c)

Fixed submission:
n=int(input())
l=[int(i) for i in input().split()]
l1=[]
c=0
l1.append(l[0])
for i in range(1,n):
  l1.append(min(l1[i-1],l[i]))
for i in range(n):
  if(l[i]==l1[i]):
    c+=1
print(c)

Buggy python submission (verdict: Runtime Error):
n=int(input())
l=[int(i) for i in input().split()]
c=0
for i in range(n):
  c1=min(l[:i+1])
  if(l[i]==c1):
    c+=1
print(c

Fixed submission:
n=int(input())
l=[int(i) for i in input().split()]
l1=[]
c=0
l1.append(l[0])
for i in range(1,n):
  l1.append(min(l1[i-1],l[i]))
for i in range(n):
  if(l[i]==l1[i]):
    c+=1
print(c)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
c=0
l=[int(i) for i in input().split()]
for i in range(n):
  c1=0
  for j in range(i+1):
    if(l[j]<l[i] and c1!=1):
      c+=1
      c1=1
print(n-c)

Fixed submission:
n=int(input())
l=[int(i) for i in input().split()]
l1=[]
c=0
l1.append(l[0])
for i in range(1,n):
  l1.append(min(l1[i-1],l[i]))
for i in range(n):
  if(l[i]==l1[i]):
    c+=1
print(c)
Buggy python submission (verdict: Runtime Error):
n,k,q=map(int,input().split())
l=[k for i in range(n)]
for j in range(q):
    k=int(input())
    for i in range(n):
        if i!=k-1:
            l[i]-=1
for i in l:
    if(i<=0):
        print("No")
    else:
        print("Yes")

Fixed submission:
s=input()
l=["Sunny","Cloudy","Rainy"]
if(s=='Rainy'):
    print("Sunny")
else:
    print(l[l.index(s)+1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.append((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])

Fixed submission:
from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.appendleft((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# for i in temp:
#     print(i)
print(temp[gy+1][gx+1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    # print(ans)
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        # if i==5:
        #     print(j,c[j],temp)
    t = cnt
    tt = ans
    # if i==8:
    #     print(temp,t)
    if t < k:
        if temp > 0:
            # print(k,t,i)
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
        else:
            j = p[i]
            for l in range(k):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        # print(ans)
    # if ans == 29779631210:
    #     print(i,ans,t,temp)
    #     exit()
print(ans)


Fixed submission:
n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    # print(ans)
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        # if i==5:
        #     print(j,c[j],temp)
    t = cnt
    tt = ans
    # if i==8:
    #     print(temp,t)
    if t < k:
        if temp > 0:
            # print(k,t,i)
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
        else:
            j = p[i]
            for l in range(t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            # print(ans)
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        # print(ans)
    # if ans == 29779631210:
    #     print(i,ans,t,temp)
    #     exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
from heapq import heappush, heappop
n = int(input())
a = []
for i in range(n):
    temp = float(input()) * (10**9)
    if temp%1 == 0:
        # print(temp)
        a.append(int(temp))
b = []
d = {0:0,1:0,2:0,3:0,4:0,5:0}
p = [[]for i in range(19)]
for i in a:
    cnt2 = 0
    cnt5 = 0
    while i%2 == 0:
        i //= 2
        cnt2 += 1
    while i%5 == 0:
        i //= 5
        cnt5 += 1
    p[min(19,cnt2)].append(-cnt5)
    # d[min(5,cnt5)] += 1
    # b.append([cnt2,cnt5])
# print(b)
# print(d)
ans = 0
for i in range(19):
    p[i] = sorted(p[i])
# print(p)
for i in range(19):
    while p[i]:
        t = p[i].pop()
        # print(t)
        # for j in p[i]:
        for k in range(max(0,18-i),19):
            # print(k,p[k],t,bisect.bisect_right(p[k],-18-t))
            ans += bisect.bisect_right(p[k],-18-t)
print(ans)
# for i in range(len(a)-1):
#     for j in range(i+1,len(a)):
#         if a[i] > 0 and a[j] > 0 and a[i]*a[j] %(10**8) == 0:
#             ans += 1
#             # print(a[i],a[j])
# print(ans)
# print(a)

Fixed submission:
import bisect
from heapq import heappush, heappop
n = int(input())
a = []
for i in range(n):
    temp = float(input()) * (10**9)
    a.append(int(temp+0.1))
b = []
d = {0:0,1:0,2:0,3:0,4:0,5:0}
p = [[]for i in range(19)]
for i in a:
    cnt2 = 0
    cnt5 = 0
    while i%2 == 0:
        i //= 2
        cnt2 += 1
    while i%5 == 0:
        i //= 5
        cnt5 += 1
    p[min(18,cnt2)].append(-cnt5)
    # d[min(5,cnt5)] += 1
    # b.append([cnt2,cnt5])
# print(b)
# print(d)
ans = 0
for i in range(19):
    p[i] = sorted(p[i])
# print(p)
for i in range(19):
    while p[i]:
        t = p[i].pop()
        # print(t)
        # for j in p[i]:
        for k in range(max(0,18-i),19):
            # print(k,p[k],t,bisect.bisect_right(p[k],-18-t))
            ans += bisect.bisect_right(p[k],-18-t)
print(ans)
# for i in range(len(a)-1):
#     for j in range(i+1,len(a)):
#         if a[i] > 0 and a[j] > 0 and a[i]*a[j] %(10**8) == 0:
#             ans += 1
#             # print(a[i],a[j])
# print(ans)
# print(a)
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil, floor
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = 0
r = 10**9
m = (l+r)//2+1
for i in range(100):
    # print(l,m,r)
    cnt = 0
    for j in a:
        cnt += (ceil(j/m)-1)
    # print(cnt)
    # print(l,m,r,cnt)
    if cnt <= k:
        r = m
        m = ceil((l+r)/2)
    else:
        l = m
        m = ceil((l+r)/2)
print(m)


Fixed submission:
from math import ceil, floor
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = 0
r = 10**9
m = (l+r)//2+1
for i in range(100):
    # print(l,m,r)
    cnt = 0
    for j in a:
        cnt += (ceil(j/m)-1)
    # print(cnt)
    # print(l,m,r,cnt)
    if cnt <= k:
        r = m
        m = ceil((l+r)/2)
    else:
        l = m
        m = ceil((l+r)/2)
print(m)