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

def main():
    N,M,K=map(int,input().split())
    MOD=998244353
    E=0

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=deque([])
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)

    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=pow(M-1,N-1-i,MOD)

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()



Fixed submission:
def main():
    N,M,K=map(int,input().split())
    MOD=998244353
    E=0

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)
    m=1
    Mk_array=[1]
    for i in range(1,N):
        m=(m*(M-1))%MOD
        Mk_array.append(m)
    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=Mk_array.pop()

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N,M,K=map(int,input().split())
    MOD=998244353
    E=0

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)

    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=pow(M-1,N-1-i,MOD)

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()



Fixed submission:
def main():
    N,M,K=map(int,input().split())
    MOD=998244353
    E=0

    n_=1
    for i in range(1,N):
        n_=(n_*i)%MOD

    nr_ = 1
    nr_array=[]
    for i in range(1,N-1):
        nr_ = (nr_ * i) % MOD
        nr_array.append(nr_)
    m=1
    Mk_array=[1]
    for i in range(1,N):
        m=(m*(M-1))%MOD
        Mk_array.append(m)
    r_=1
    for i in range(0,K+1):
        if i!=0 and i!=N-1:
            r_ = (r_ * i) % MOD
            nr_=nr_array.pop()
            power_r=pow(r_,MOD-2,MOD)
            power_nr=pow(nr_,MOD-2,MOD)
        Mk=Mk_array.pop()

        if i!=0 and i!=N-1:
            E+=(n_*power_r*power_nr*Mk)%MOD
        else:
            E+=Mk%MOD

    res=(M*E)%MOD
    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#j-i=Ai+Aj(j>i)
#j-Aj=Ai+i

#Lj=Ri=X
from bisect import bisect_left

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

    L={}
    R={}
    for i in range(N):
        l=(i+1)-A[i]
        r=A[i]+i+1
        if (l in L.keys()):
            L[l].append(i+1)
        else:
            L[l]=[i+1]
        if (r in R.keys()):
            R[r].append(i+1)
        else:
            R[r]=[i+1]
    
    L_zip=zip(L.keys(),L.values())
    R_zip=zip(R.keys(),R.values())

    L_zip=sorted(L_zip)
    R_zip=sorted(R_zip)

    R_key,R_value=zip(*R_zip)

    res=0


    for l,l_index in L_zip:
        if l>0:
            ind=bisect_left(R_key ,l)
            if R_key[ind]==l:
                for l in l_index:
                    for r in R_value[ind]:
                        if l>r:
                            res+=1
            if ind>=1:
                R_key=R_key[ind-1:]
                R_value=R_value[ind-1:]

    print(res)

if __name__=="__main__":
    main()





Fixed submission:
#j-i=Ai+Aj(j>i)
#j-Aj=Ai+i

#Lj=Ri=X
from bisect import bisect_left

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

    L={}
    R={}

    res=0

    for i in range(N):
        l=(i+1)-A[i]
        r=A[i]+i+1
        if (l in R.keys()):
            res+=len(R[l])
        if (r in R.keys()):
            R[r].append(i+1)
        else:
            R[r]=[i+1]


    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=S
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

    for i in range(1,N):
        print(min(dp[i]))




if __name__=="__main__":
    main()

Fixed submission:
from heapq import heappop,heappush

def main():
    N,M,S=map(int,input().split())
    G=[[] for _ in range(N)]
    for i in range(M):
        U,V,A,B=map(int,input().split())
        G[U-1].append([V-1,A,B])
        G[V-1].append([U-1,A,B])
    C=[]
    D=[]
    for _ in range(N):
        c,d=map(int,input().split())
        C.append(c)
        D.append(d)

    MaxMoney=2500

    dp=[[float('inf') for __ in range(MaxMoney+1)] for _ in range(N)]

    cost=0
    money=min(S,MaxMoney)
    que=[]
    heappush(que,(cost,0,money)) #cost,node,money
    dp[0][money] = 0

    while len(que)>0:
        cost,node,money=heappop(que)

        stop_money=min(money+C[node],MaxMoney)
        stop_cost=cost+D[node]
        if stop_cost<dp[node][stop_money]:
            dp[node][stop_money]=stop_cost
            heappush(que,(stop_cost,node,stop_money))

        for to_node,to_money,to_cost in G[node]:
            money_=min(money-to_money,MaxMoney)
            if money_<0:
                continue
            cost_=cost+to_cost
            if dp[to_node][money_]<=cost_:
                continue

            dp[to_node][money_]=cost_
            heappush(que,(cost_,to_node,money_))

    for i in range(1,N):
        print(min(dp[i]))




if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N=int(input())
    A=list(map(int,input().split()))

    dp=[[0 for i in range(N+1)] for _ in range(N+1)]

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()


Fixed submission:
def main():
    N=int(input())
    A=list(map(int,input().split()))

    dp=[[0 for i in range(N+1)] for _ in range(N+1)]

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()

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

    dp=[[0 for i in range(N+1)] for _ in range(N+1)]

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            scoreLeft=dp[i+1][j]
            score=dp[i][j]

            if (scoreLeft<score+A[i+j]*(A_index[i+j]-i)):
                dp[i+1][j]=score+A[i+j]*(A_index[i+j]-i)

            scoreRight=dp[i][j+1]

            if (scoreRight<score+A[i+j]*((N-1-j)-A_index[i+j])):
                dp[i][j+1]=score+A[i+j]*((N-1-j)-A_index[i+j])

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()


Fixed submission:
def main():
    N=int(input())
    A=list(map(int,input().split()))

    dp=[[0 for i in range(N+1)] for _ in range(N+1)]

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

    res=0
    for i in range(N+1):
        res=max(res,dp[i][N-i])

    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def main():
    N,K,C=map(int,input().split())
    S=input()

    Left=[]
    Right=[]

    counter=0
    while counter<N and len(Left)<K:
        if S[counter]=="o":
            if len(Left)<K:
                Left.append(counter)
                counter+=C
        counter+=1

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.insert(0,counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        if Right[i]==Left[i]:
            print(Right[i]+1)

if __name__=="__main__":
    main()

Fixed submission:
import sys
from collections import deque

def main():
    N,K,C=map(int,input().split())
    S=input()

    Left=deque([])
    Right=deque([])

    counter=0
    while counter<N and len(Left)<K:
        if S[counter]=="o":
            if len(Left)<K:
                Left.append(counter)
                counter+=C
        counter+=1

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.appendleft(counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        l=Left.popleft()
        r=Right.popleft()
        if l==r:
            print(l+1)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    inp=list(map(lambda x:int(x),input().split()))
    A=inp[0]
    B=inp[1]

    res=B
    if 6<=B=<12:
        res=res//2
    elif B<=5:
        res=0

    print(res)

if __name__=="__main__":
    main()
    


Fixed submission:
def main():
    inp=list(map(lambda x:int(x),input().split()))
    A=inp[0]
    B=inp[1]

    res=B
    if A>=6 and A<=12:
        res=res//2
    elif A<=5:
        res=0

    print(res)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from heapq import heappush,heappop
def main():
    Q=int(input())

    ab_list=[]
    query_type=[]

    for i in range(Q):
        query=list(map(int,input().split()))
        query_type.append(query[0])
        if query[0]==1:
            ab_list.append((query[1],query[2]))

    #query_type->[1,1,2,1,2]
    #ab_list->[(a,b),(a,b),(a,b)]

    L=[]
    R=[]

    ini=0

    counter=0
    ab_pointer=0
    minF=0
    for i in query_type:
        if i==1:
            if counter==0:
                ini=ab_list[ab_pointer][0]
                counter+=1
                minF+=ab_list[ab_pointer][1]
            elif counter==1:
                L.append(-1*min(ini,ab_list[ab_pointer][0]))
                R.append(max(ini,ab_list[ab_pointer][0]))
                counter+=1
                delta=abs(-1*L[0]-R[0])
                minF+=delta+ab_list[ab_pointer][1]
            else:
                a_new=ab_list[ab_pointer][0]
                b_new=ab_list[ab_pointer][1]
                heappush(L,-1*a_new)
                heappush(R,a_new)
                Lmax=-1*heappop(L)
                Rmin=heappop(R)
                if Lmax<=Rmin:
                    heappush(L,-1*Lmax)
                    heappush(R,Rmin)
                else:
                    heappush(L,-1*Rmin)
                    heappush(R,Lmax)
                delta=abs(Lmax-Rmin)
                minF+=delta+b_new
            ab_pointer+=1
        else:
            if counter<=1:
                print(str(ini)+" "+str(minF))
            else:
                print(str(-1*heappop(L))+" "+str(minF))



if __name__=="__main__":
    main()





Fixed submission:
from heapq import heappush,heappop
def main():
    Q=int(input())

    ab_list=[]
    query_type=[]

    for i in range(Q):
        query=list(map(int,input().split()))
        query_type.append(query[0])
        if query[0]==1:
            ab_list.append((query[1],query[2]))

    #query_type->[1,1,2,1,2]
    #ab_list->[(a,b),(a,b),(a,b)]

    L=[]
    R=[]

    ini=0

    counter=0
    ab_pointer=0
    minF=0
    for i in query_type:
        if i==1:
            a_new=ab_list[ab_pointer][0]
            b_new=ab_list[ab_pointer][1]
            heappush(L,-1*a_new)
            heappush(R,a_new)
            Lmax=-1*heappop(L)
            Rmin=heappop(R)
            if Lmax<=Rmin:
                heappush(L,-1*Lmax)
                heappush(R,Rmin)
            else:
                heappush(L,-1*Rmin)
                heappush(R,Lmax)
            delta=abs(Lmax-Rmin)
            minF+=delta+b_new
            ab_pointer+=1
        else:
            minX=-1*heappop(L)
            print(str(minX)+" "+str(minF))
            heappush(L,-1*minX)



if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = set()
    for i in range(K):
        _l, _r = map(int, input().split())
        _s = set(list(range(_l, _r+1)))
        S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        for d in S:
            if i-d > 0:
                dp[i] = (dp[i] + dp[i-d]) % MOD
    print(dp[N])


solve()


Fixed submission:

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    LR_L = [[int(x) for x in input().split()] for y in range(K)]
    # S = set()
    # for i in range(K):
    #     _l, _r = map(int, input().split())
    #     _s = set(list(range(_l, _r+1)))
    #     S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        # for d in S:
        #     if i-d > 0:
        #         dp[i] = (dp[i] + dp[i-d]) % MOD
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print(dp[N])


solve()

Buggy python submission (verdict: Time Limit Exceeded):

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = set()
    for i in range(K):
        _l, _r = map(int, input().split())
        _s = set(list(range(_l, _r+1)))
        S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        for d in S:
            if i-d > 0:
                dp[i] = (dp[i] + dp[i-d]) % MOD
    print(dp[N])


solve()


Fixed submission:

def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    LR_L = [[int(x) for x in input().split()] for y in range(K)]
    # S = set()
    # for i in range(K):
    #     _l, _r = map(int, input().split())
    #     _s = set(list(range(_l, _r+1)))
    #     S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        # for d in S:
        #     if i-d > 0:
        #         dp[i] = (dp[i] + dp[i-d]) % MOD
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print(dp[N])


solve()
Buggy python submission (verdict: Time Limit Exceeded):

def solve():
    N, X, M = map(int, input().split())

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()


Fixed submission:

def solve():
    N, X, M = map(int, input().split())

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

input = sys.stdin.readline


def solve():
    MOD = 10**9+7
    N = int(input())
    A_L = [int(x) for x in input().split()]
    ans = 0
    for i, ai in enumerate(A_L):
        for j in range(i+1, N):
            aj = A_L[j]
            ans = (ans + ai * aj) % MOD

    print(ans)


solve()


Fixed submission:
import sys

input = sys.stdin.readline


def solve():
    MOD = 10**9+7
    N = int(input())
    A_L = tuple(int(x) for x in input().split())
    cum_a_l = [0] * N
    cum_a_l[0] = A_L[0]
    for i in range(1, N):
        cum_a_l[i] = (cum_a_l[i-1] + A_L[i]) % MOD
    ans = 0

    for i in range(N-1, 0, -1):
        ans = (ans + cum_a_l[i-1]*A_L[i] % MOD) % MOD
    print(ans)


solve()
Buggy python submission (verdict: Time Limit Exceeded):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def solve():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for i in range(M):
        _a, _b = map(int, input().split())
        UF.union(_a-1, _b-1)
    rt_l = UF.roots()
    ans = 0
    for _rt in rt_l:
        _len = len(UF.members(_rt))
        if ans < _len:
            ans = _len

    print(ans)


solve()


Fixed submission:

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def solve():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for i in range(M):
        _a, _b = map(int, input().split())
        UF.union(_a-1, _b-1)
    rt_l = UF.roots()
    ans = 0
    for _rt in rt_l:
        _len = UF.size(_rt)
        if ans < _len:
            ans = _len

    print(ans)


solve()
Buggy python submission (verdict: Runtime Error):
# A

n = int(input())
a_l = [int(float(input()) * 10**9) for x in range(n)]

list = [[0] * 18 for x in range(18)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]
    
ans = 0
for i in range(n):
    _t,_f = b_l[i]
    for j in range(18-_t,19):
        for k in range(18-_f,19):
            ans += list[j][k]
    if _t >= 9 and _f >= 9:
        ans -= 1
        
print(ans // 2)


Fixed submission:
# A

from decimal import *

n = int(input())
a_l = [int(Decimal(input()) * 10**9) for x in range(n)]

list = [[0] * 19 for _ in range(19)]
cs_list = [[0] * 19 for _ in range(19)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]

for i in range(19):
    for j in range(19):
        for k in range(i+1):
            for l in range(j+1):
                cs_list[k][l] += list[i][j]

ans = 0
for i in range(n):
    _t,_f = b_l[i]
    if _t >= 9 and _f >= 9:
        ans -= 1
    ans += cs_list[18-_t][18-_f]
        
print(ans // 2)