Problem:


Score : 300 points

Problem Statement

You are given N real values A_1, A_2, \ldots, A_N.
Compute the number of pairs of indices (i, j)
    such that i < j and the product A_i \cdot A_j is integer.

Constraints

2 \leq N \leq 200\,000

0 < A_i < 10^4

A_i is given with at most 9 digits after the decimal.

Input

Input is given from Standard Input in the following format.

N
A_1
A_2
\vdots
A_N

Output

Print the number of pairs with integer product A_i \cdot A_j (and i < j).

Sample Input 1

5
7.5
2.4
17.000000001
17
16.000000000

Sample Output 1

3

There are 3 pairs with integer product:

7.5 \cdot 2.4 = 18

7.5 \cdot 16 = 120

17 \cdot 16 = 272

Sample Input 2

11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001

Sample Output 2

8



Sample input:
5
7.5
2.4
17.000000001
17
16.000000000


Sample output:
3

Submission status: Wrong Answer

Solution code:
import math

cand = list(set([2**x * 5**y for x in range(18)
                 for y in range(8) if 2**x * 5**y <= 200000]))
cand.sort()


def f(n):
    for i in cand:
        x = n * i
        if x.is_integer():
            return i
    else:
        return None


def div(n, bl=True):
    if n is None:
        return (-1, -1)
    if n == -1:
        return (-1, -1)
    if n == 10**9 + 1:
        return (False, False)
    elif bl and not n.is_integer():
        return (0, 0)
    else:
        n = int(n)
        two = format(n, 'b')[::-1].find('1')
        if two < 0:
            return(-1, -1)
        n = n >> two
        cnt = 0
        while n % 5 == 0:
            n //= 5
            cnt += 1
        return (two, cnt)


n = int(input())
arr = [float(input()) for _ in range(n)]
arr = [x for x in arr if min(
    x - int(x), math.ceil(x) - x) >= 0.000005 or x == int(x)]

x = [div(x) for x in arr]
y = [div(x, False) for x in [f(x) for x in arr]]
z = [div(x * 2**y1 * 5**z, False) for x, (y1, z) in zip(arr, y)]


ans = 0
for i in range(len(y)):
    for j in range(i + 1, len(y)):
        (a, b), (c, d) = y[i], y[j]
        if a == -1 or b == -1 or c == -1 or d == -1:
            continue
        elif a == 0 and b == 0 and c == 0 and d == 0:
            ans += 1
        elif a + c <= z[i][0] + z[j][0] and b + d <= z[i][1] + z[j][1]:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(float(input()))

cnt = 0

for i in range(n):
    i1 = i+1
    if i == n-1:
        break
    for j in range(i1, n):
        b = a[i]*a[j]
        if b.is_integer():
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

int_cnt = 0
int_25 = [[0 for _ in range(10)] for _ in range(10)]
float_25 = [[0 for _ in range(10)] for _ in range(10)]
float_2 = [[0 for _ in range(10)] for _ in range(10)]
float_5 = [[0 for _ in range(10)] for _ in range(10)]

for _ in range(n):
    a = float(input())
    if a % 1 == 0:
        int_cnt += 1
        t = 0
        while a % 2 == 0:
            a //= 2
            t += 1
        t = min(t, 9)
        f = 0
        while a % 5 == 0:
            a //= 5
            f += 1
        f = min(f, 9)
        int_25[t][f] += 1
    else:
        a *= 10 ** 9
        a = int(a)
        cnt = 9
        while a % 10 == 0:
            a //= 10
            cnt -= 1
        t = 0
        while a % 2 == 0:
            a //= 2
            t += 1
        f = 0
        while a % 5 == 0:
            a //= 5
            f += 1
        tt = max(t - cnt + 1, 0)
        ff = max(f - cnt + 1, 0)
        tt = min(tt, 9)
        ff = min(ff, 9)
        float_25[max(0, cnt - t)][max(0, cnt - f)] += 1
        float_2[tt][max(0, cnt - f)] += 1
        float_5[max(0, cnt - t)][ff] += 1
ans = int_cnt * (int_cnt - 1) // 2
for i in range(10):
    for j in range(10):
        for k in range(i + 1):
            for l in range(j + 1):
                ans += int_25[i][j] * float_25[k][l]

for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                if (i - j >= 0) and (k - l >= 0):
                    if i == j == k == l:
                        continue
                        
                    ans += float_2[i][l] * float_5[j][k]
                    
    
print(ans)

Submission status: Wrong Answer

Solution code:
import pprint
N=int(input())
l2=[]
bit2=50
bit5=22
#table=[[0 for _ in range(20)] for _ in range(15)]
#table=[[0 for _ in range(45)] for _ in range(20)]
table=[[0 for _ in range(bit2)] for _ in range(bit5)]
for i in range(N):
    n=float(input())
    #print(n)
    n=int(n*pow(10,10))
    count2=0
    count5=0
    #print(n,kake)
    while n==2*(n//2):
        n=n//2
        count2=count2+1
    while n==5*(n//5):
        n=n//5
        count5=count5+1
    table[count5][count2]=table[count5][count2]+1
    l2.append([count2,count5])
#pprint.pprint(table)
#print(l2)
ans=0
for i in range(bit5):
    for j in range(bit2):
        num=table[i][j]
        min2=max(0,20-j)
        min5=max(0,20-i)
        cnt=0
        if num>0:
            #print(min2,min5,i,j,num)
            for k in range(min5,bit5):
                for l in range(min2,bit2):
                    cnt=cnt+table[k][l]
            if (min2<=j)and(min5<=i):
                cnt=cnt-1
            ans=ans+num*cnt
            #print(ans)
print(ans//2)

Submission status: Wrong Answer

Solution code:
def five(x):
    cnt1 = 0
    while x%5==0:
        cnt1+= 1
        x = x//5
    cnt2 = 0
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (cnt1, cnt2)

N = int(input())

F = []
for i in range(N):
    A = float(input())
    A = int(A*(10**9))
    F.append(five(A))

F.sort()
# print(F)
j = 0
temp = 0
dp = [0]*19
k = 0
for i in range(N-1):
    if N-1-j < i:
        dp[min(F[i][1], 18)] -= 1
        # print(i, N - j - 1, dp)
    while N-1-j> i and F[i][0]+F[N-1-j][0] >= 18:
        dp[min(F[N-1-j][1],18)] += 1
        # print(i, N - j - 1, dp)
        j += 1
    k = sum(dp[:18-F[i][1]])
    temp += min(j, N-i-1) - k
    # print(j, N-i-1, k)

print(temp)

"""
3
0.1
0.1
10
"""

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

AS = [input().strip() for _ in range(N)]

nums = [int(a.replace('.', '')) for a in AS]
dens = [1 if '.' not in a else 10**(len(a) - a.index('.') - 1) for a in AS]

# print(nums, dens)

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a%b)

gs = [gcd(num, den) for num, den in zip(nums, dens)]
nums = [num // g for num, g in zip(nums, gs)]
dens = [den // g for den, g in zip(dens, gs)]

def signature(n):
    e2, e5 = 0, 0
    while n % 2 == 0:
        n //= 2
        e2 += 1
    while n % 5 == 0:
        n //= 2
        e5 += 1
    return (e2, e5)

lookup = defaultdict(int)
for num, den in zip(nums, dens):
    n2, n5 = signature(num)
    d2, d5 = signature(den)
    lookup[(n2-d2, n5-d5)]+=1

ans = 0
for k1 in lookup:
    for k2 in lookup:
        v1, v2 = lookup[k1], lookup[k2]
        x1, y1 = k1
        x2, y2 = k2
        if x1 + x2 >= 0 and y1 + y2 >=0:
            if k1 == k2:
                ans += v1*(v1-1)
            else:
                ans += v1*v2

ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction

n=int(input())

num=[]
twoP=[]
fiveP=[]
e=[]

num_num=[[0 for i in range(6)]for j in range(6)]
two_num=[0 for i in range(60)]
five_num=[0 for i in range(60)]


for i in range(n):
    s=input()
    if "." in s: 
        b=len(s.split(".")[1])
    else:
        b=0
    s=int(s.replace(".",""))
    a=Fraction(s,10**b)

    if a.denominator==1:
        num.append(a)
        c=a.numerator
        two=0
        five=0
        while c%2==0:
            c//=2
            two+=1
        while c%5==0:
            c//=5
            five+=1

        # num_num[two][five]+=1
        # two_num[two]+=1
        # five_num[five]+=1
    elif a.denominator%2==0 and a.denominator%5==0:
        e.append(a)
    elif a.denominator%5==0:
        fiveP.append(a)
        c=a.numerator
        two=0
        # while c%2==0:
        #     c//=2
        #     two+=1
        # two_num[two]+=1

    else:
        twoP.append(a)
        c=a.numerator
        five=0
        # while c%5==0:
        #     c//=5
        #     five+=1
        # five_num[five]+=1
ans= len(num)*(len(num)-1)//2
# print(ans)
for a in twoP:
    c=a.denominator
    count=0
    while c%2==0:
        count+=1
        c//=2
    # print(count,c)
    if count>=50:
        continue
    for i in range(count,50):
        ans+=two_num[i]
# print(ans)

for a in fiveP:
    c=a.denominator
    count=0
    while c%5==0:
        count+=1
        c//=5
    if count>=49:
        continue
    for i in range(count,50):
        ans +=five_num[i]
# print(ans)
for a in e:
    c=a.denominator
    c2,c5=0,0
    while c%2==0:
        c//=2
        c2+=1
    while c%5==0:
        c//=5
        c5+=1
    if c2>=5 or c5>=5:
        continue
    for i in range(c2,4):
        for j in range(c5,4):
            ans+=num_num[i][j]


for a1 in twoP:
    if a1.numerator%5!=0:
        continue
    for a2 in fiveP:
        if a1.numerator%a2.denominator==0 and a2.numerator%a1.denominator==0:
            ans+=1


print(ans)
# print(num)
# print(twoP)
# print(fiveP)
# print(e)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
D = defaultdict(lambda:defaultdict(int))
for j in range(n):
    a = Decimal(input())
    cnt1 = 0
    cnt2 = 0
    while a % 1:
        a *= 10
        cnt1 -= 1
        cnt2 -= 1
    while a % 2 == 0:
        a /= 2
        cnt1 += 1
    while a % 5 == 0:
        a /= 5
        cnt2 += 1
    D[cnt1][cnt2] += 1

ans = 0
for i in range(-15, 20):
    for k in range(-15, 25):
        for j in range(-7, 13):
            for l in range(-7, 13):
                if i + k >= 0 and j + l >= 0:
                    if i == k and j == l:
                        ans += D[i][j] * (D[k][l] - 1)
                    else:
                        ans += D[i][j] * D[k][l]

print(ans // 2)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = [float(input()) for i in range(N)]

counter = Counter()

for i in range(N):
    tmp = round(A[i]*100000000,5)
    # print(tmp)
    if tmp.is_integer():
        
        tmp = int(tmp)
        cnt2 = 0
        cnt5 = 0
        while tmp%2 == 0:
            tmp //= 2
            cnt2 += 1
        while tmp%5 == 0:
            tmp //= 5
            cnt5 += 1
        # print(cnt2,cnt5)
        counter[(cnt2,cnt5)] += 1
ans = 0
# print(counter)
for i in range(48):
    for j in range(25):
        for a in range(16-i,48):
            for b in range(16-j,25):
                if i == a and j == b:
                    ans += counter[(i,j)]*(counter[(i,j)]-1)
                    # if counter[(i,j)]*(counter[(i,j)]-1):
                    #     print(i,j,a,b,counter[(i,j)]*(counter[(i,j)]-1))
                else:
                    ans += counter[(i,j)]*counter[(a,b)]
                    # if counter[(i,j)]*counter[(a,b)]:
                    #     print(i,j,a,b,counter[(i,j)]*counter[(a,b)])
print(ans//2)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal
n=int(input())
A=[float(input()) for _ in range(n)]
multiple=[]
count=0
for i in range(1,n):
    for j in range(n-i):
        ans=Decimal(A[i-1]*A[i+j])
        if float(ans).is_integer():
            multiple.append(ans)
        count+=1
print(len(multiple))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f
import random
class rh:#base,max_n=ありうる文字の最大長,convertを指定すること
    def __init__(self,base,max_n):#baseとmaxnを指定すること。baseは偶数(modが奇数)
        self.mod=random.randrange(1<<54-1,1<<55-1,2)#奇数、衝突させられないよう乱数で生成
        self.base=int(base*0.5+0.5)*2#偶数,英小文字なら26とか
        self.max_n=max_n
        self.pows1=[1]*(max_n+1)
        cur1=1
        for i in range(1,max_n+1):
            cur1=cur1*base%self.mod
            self.pows1[i]=cur1

    def convert(self,c): return alp2num(c,False)#大文字の場合Trueにする
    
    def get(self, s):#特定の文字のhash. O(|s|)
        n=len(s)
        mod=self.mod
        si=[self.convert(ss) for ss in s]
        h1=0
        for i in range(n):h1=(h1+si[i]*self.pows1[n-1-i])%mod
        return h1
    
    def get_roll(self, s, k, uroboros=False):#ローリングハッシュ,sの各文字を始点とした長さkの部分文字のhash値をすべて得る,O(|s|)
        #uroboros: trueの場合文字sを循環させ、n個のハッシュ値を得る。 falseの場合n-k+1個
        n=len(s)
        maxitr=n-k+1
        if uroboros: maxitr=n
    
        si=[self.convert(ss) for ss in s]
        mod=self.mod
        h1=0
        for i in range(k):h1=(h1+si[i%n]*self.pows1[k-1-i])%mod
        hs=[0]*maxitr
        hs[0]=h1
        mbase1=self.pows1[k]
        base=self.base
        
        for i in range(1,maxitr): 
            front=si[i-1];back=si[(i+k-1)%n]
            h1=(h1*base-front*mbase1+back)%mod
            hs[i]=h1
        return hs

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    mod=1000000007
    mod2=999999937

    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    L=["" for _ in range(N)]
    ll=[0]*N
    for i in range(N):
        s=input()
        ls=len(s)
        ll[i]=ls
        L[i]=s

    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    inds=argsort(ll)
    d=Counter()
    ans=0
    base=27

    for im in inds:
        
        s=L[im]

        ls=len(s)
        cur=0
        cur2=0
        se=Counter(s)
        #printe(se)
        for i in range(ls):
            for a,val in se.items():
                if val:
                    ai=alp2num(a)
                    ans+=d[(i+1,(cur*base+ai)%mod,(cur2*base+ai)%mod2)]
                    
            si=s[-1-i]
            sin=alp2num(si)
            cur=(cur*base+sin)%mod
            cur2=(cur2*base+sin)%mod2

            se[si]-=1

        d[(ls,cur,cur2)]+=1

    print(ans)
            





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    from collections import defaultdict
    from fractions import Fraction
    n = int(input())
    d = defaultdict(int)
    ans0 = 0
    for i in range(n):
        x = Fraction(input())
        cnt0, cnt5, cnt2 = 0, 0, 0
        for j in range(5):
            if x % 1 == 0:
                break
            else:
                x *= 10
                cnt0 += 1
        if cnt0 == 5:
            continue
        for j in range(4):
            if x % 5 != 0:
                break
            else:
                x //= 5
                cnt5 += 1
        for j in range(4):
            if x % 2 != 0:
                break
            else:
                x //= 2
                cnt2 += 1
        d[(cnt0, cnt2, cnt5)] += 1
        ans0 += cnt0
    lis = list(d)
    ans_f = 0
    for i, (a, b, c) in enumerate(lis):
        if a == 0:
            continue
        k = d[(a, b, c)]
        l = 0
        for x, y, z in lis[i:]:
            if a == x and b == y and c == z:
                continue
            if b + y >= a and c + z >= a:
                l += d[(x, y, z)]
        ans_f += k * l
    print((ans0 * (ans0 - 1)) // 2 + ans_f)
    
    return
solve()

Submission status: Wrong Answer

Solution code:
from decimal import Decimal, getcontext
getcontext().prec = 30

def five(x):
    cnt1 = 0
    while x%5==0:
        cnt1+= 1
        x = x//5
    cnt2 = 0
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (cnt1, cnt2)

N = int(input())

F = []
for i in range(N):
    A = float(input())
    A = int(A*(10**9))
    F.append(five(A))
exit()

F.sort()
# print(F)
j = 0
temp = 0
dp = [0]*19
k = 0
for i in range(N-1):
    if N-1-j < i:
        dp[min(F[i][1], 18)] -= 1
        # print(i, N - j - 1, dp)
    while N-1-j> i and F[i][0]+F[N-1-j][0] >= 18:
        dp[min(F[N-1-j][1],18)] += 1
        # print(i, N - j - 1, dp)
        j += 1
    k = sum(dp[:18-F[i][1]])
    temp += min(j, N-i-1) - k
    # print(j, N-i-1, k)

print(temp)

"""
3
0.1
0.1
10
"""

Submission status: Wrong Answer

Solution code:
import re
import sys
import numpy as np
import copy
from collections import deque
input = sys.stdin.readline
np.set_printoptions(precision=9)


def print_ans(N, ar):
    """Test Case
    >>> print_ans(5,[7.5,2.4,17.000000001,17,16.000000000])
    3
    >>> print_ans(11,[0.9,1,1,1.25,2.30000,5,70,0.000000001,9999.999999999,0.999999999,1.000000001])
    8
    """
    ar = deque(ar)
    array = deque()
    array.append(np.array(ar, dtype='float64'))
    for i in range(N-1):
        tmp = ar.popleft()
        ar.append(tmp)
        array.append(np.array(ar, dtype='float64'))
    array = np.array(array)
    ans = 0
    for i in range(N-1):
        a1 = array[i, 0]
        a2 = array[i, 1:N-i] 
        tmp_list = a1 * a2
        tmp_list = tmp_list
        ans += np.count_nonzero(tmp_list == tmp_list.astype('int'))
    print(ans)


if __name__ == '__main__':
    N = int(input().rstrip())
    ar = [float(input().rstrip()) for _ in range(N)]
    print_ans(N, ar)

Submission status: Wrong Answer

Solution code:
from decimal import Decimal, getcontext
getcontext().prec = 30

def five(x):
    cnt1 = 0
    cnt2 = 0
    while x%10==0:
        cnt1+= 1
        cnt2 += 1
        x = x//10
    while x%5==0:
        cnt1+= 1
        x = x//5
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (cnt1, cnt2)


N = int(input())

F = []
for i in range(N):
    A = Decimal(input())
    A = int(A*(10**9))
    F.append(five(A))
exit()

F.sort()
# print(F)
j = 0
temp = 0
dp = [0]*19
k = 0
for i in range(N-1):
    if N-1-j < i:
        dp[min(F[i][1], 18)] -= 1
        # print(i, N - j - 1, dp)
    while N-1-j> i and F[i][0]+F[N-1-j][0] >= 18:
        dp[min(F[N-1-j][1],18)] += 1
        # print(i, N - j - 1, dp)
        j += 1
    k = sum(dp[:18-F[i][1]])
    temp += min(j, N-i-1) - k
    # print(j, N-i-1, k)

print(temp)

"""
3
0.1
0.1
10
"""

Submission status: Wrong Answer

Solution code:
from decimal import Decimal
n=11
A=[0.9,1,1,1.25,2.30000,5,70,0.000000001,9999.999999999,0.999999999,1.000000001]
multiple=[]
for i in range(1,n):
    for j in range(n-i):
        ans=Decimal(A[i-1]*A[i+j])
        if float(ans).is_integer():
            multiple.append(ans)
print(len(multiple))

Submission status: Wrong Answer

Solution code:
from decimal import Decimal, getcontext
getcontext().prec = 30

def five(x):
    cnt1 = 0
    cnt2 = 0
    while x%10==0:
        cnt1+= 1
        cnt2 += 1
        x = x//10
    while x%5==0:
        cnt1+= 1
        x = x//5
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (cnt1, cnt2)

exit()
N = int(input())

F = []
for i in range(N):
    A = Decimal(input())
    A = int(A*(10**9))
    F.append(five(A))
exit()

F.sort()
# print(F)
j = 0
temp = 0
dp = [0]*19
k = 0
for i in range(N-1):
    if N-1-j < i:
        dp[min(F[i][1], 18)] -= 1
        # print(i, N - j - 1, dp)
    while N-1-j> i and F[i][0]+F[N-1-j][0] >= 18:
        dp[min(F[N-1-j][1],18)] += 1
        # print(i, N - j - 1, dp)
        j += 1
    k = sum(dp[:18-F[i][1]])
    temp += min(j, N-i-1) - k
    # print(j, N-i-1, k)

print(temp)

"""
3
0.1
0.1
10
"""

Submission status: Wrong Answer

Solution code:
n = int(input())

int_cnt = 0
int_25 = [[0 for _ in range(10)] for _ in range(10)]
float_25 = [[0 for _ in range(10)] for _ in range(10)]
float_2 = [[0 for _ in range(10)] for _ in range(10)]
float_5 = [[0 for _ in range(10)] for _ in range(10)]

for _ in range(n):
    a = float(input())
    if a % 1 == 0:
        int_cnt += 1
        t = 0
        while a % 2 == 0:
            a //= 2
            t += 1
        t = min(t, 9)
        f = 0
        while a % 5 == 0:
            a //= 5
            f += 1
        f = min(f, 9)
        int_25[t][f] += 1
    else:
        a *= 10 ** 9
        a = int(a)
        cnt = 9
        while a % 10 == 0:
            a //= 10
            cnt -= 1
        t = 0
        while a % 2 == 0:
            a //= 2
            t += 1
        f = 0
        while a % 5 == 0:
            a //= 5
            f += 1
        tt = max(t - cnt, 0)
        ff = max(f - cnt, 0)
        tt = min(tt, 9)
        ff = min(ff, 9)
        float_25[max(0, cnt - t)][max(0, cnt - f)] += 1
        float_2[tt][max(0, cnt - f)] += 1
        float_5[max(0, cnt - t)][ff] += 1
ans = int_cnt * (int_cnt - 1) // 2
for i in range(10):
    for j in range(10):
        for k in range(i + 1):
            for l in range(j + 1):
                ans += int_25[i][j] * float_25[k][l]

for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                if (i - j >= 0) and (k - l >= 0):
                    if i == j == l == l == 0:
                        continue
                    ans += float_2[i][l] * float_5[j][k]
                    
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
readline = input

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

from fractions import Fraction

@mt
def slv(N, A):
    d = defaultdict(Counter)
    d5 = defaultdict(Counter)
    de = defaultdict(Counter)
    nd = Counter()
    for a in A:
        a += '.0'
        t = a.split('.')
        b = int(t[0]) * 10**9 + int(t[1]) * 10**(9- len(t[1]))
        e = str(b)
        for i in range(100):
            if e[-(i+1)] != '0':
                break

        d[i][b] += 1
        if e[-(i+1)] == '5':
            d5[i][b] += 1
        elif int(e[-(i+1)]) % 2 == 0:
            de[i][b] += 1
        nd[i] += 1

    ans = 0
    rk = sorted(d.keys(), reverse=True)
    for k, kk in combinations(rk, r=2):
        nk = nd[k]
        nkk = nd[kk]
        if k + kk >= 18:
            ans += nk * nkk
        elif k + kk > 5:
            for av, an in d5[k].items():
                for bv, bn in de[kk].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
            for av, an in de[k].items():
                for bv, bn in d5[kk].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
    for k in rk:
        nk = nd[k]
        if 2*k >= 18:
            ans += nk * (nk-1) // 2
        elif k + k > 5:
            for av, an in d5[k].items():
                for bv, bn in de[k].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
    return ans


def ref(N, A):
    B = []
    for a in A:
        t = a.split('.')
        b = 0
        if len(t) == 1:
            b = int(t[0]) * 10**9
        else:
            b = int(t[0]) * 10**9 + int(t[1]) * 10**(9 - len(t[1]))
        B.append(b)

    ans = 0
    for a, b in combinations(B, r=2):
        if (a * b ) % 10**18 == 0:
            print(a, b)
            ans += 1
    return ans

def main():
    N = read_int()
    A = [input() for _ in range(N)]
    print(slv(N, A))
    # print(ref(N, A))

    # N = 2 * 10**5
    # for _ in range(1000):
    #     A = []
    #     for _ in range(N):
    #         b = str(random.randint(1, 10)) + '.' + str(random.randint(0, 10**9))
    #         A.append(b)

    #     a = slv(N, A)
    #     # b = ref(N, A)
    #     # print(a, b)
    #     # if a != b:
    #     #     print(a, b)
    #     #     print(A)
    #     #     break



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
readline = input

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

from fractions import Fraction

@mt
def slv(N, A):
    d = defaultdict(Counter)
    d5 = defaultdict(Counter)
    de = defaultdict(Counter)
    nd = Counter()
    for a in A:
        a += '.0'
        t = a.split('.')
        b = int(t[0]) * 10**9 + int(t[1]) * 10**(9- len(t[1]))
        e = str(b)
        for i in range(100):
            if e[-(i+1)] != '0':
                break

        d[i][b] += 1
        if e[-(i+1)] == '5':
            d5[i][b] += 1
        elif int(e[-(i+1)]) % 2 == 0:
            de[i][b] += 1
        nd[i] += 1

    ans = 0
    rk = sorted(d.keys(), reverse=True)
    for k, kk in combinations(rk, r=2):
        nk = nd[k]
        nkk = nd[kk]
        if k + kk >= 18:
            ans += nk * nkk
        elif k + kk > 10:
            for av, an in d5[k].items():
                for bv, bn in de[kk].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
            for av, an in de[k].items():
                for bv, bn in d5[kk].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
    for k in rk:
        nk = nd[k]
        if 2*k >= 18:
            ans += nk * (nk-1) // 2
        elif k + k > 10:
            for av, an in d5[k].items():
                for bv, bn in de[k].items():
                    if (av * bv) % 10**18 == 0:
                        ans += an * bn
    return ans


def ref(N, A):
    B = []
    for a in A:
        t = a.split('.')
        b = 0
        if len(t) == 1:
            b = int(t[0]) * 10**9
        else:
            b = int(t[0]) * 10**9 + int(t[1]) * 10**(9 - len(t[1]))
        B.append(b)

    ans = 0
    for a, b in combinations(B, r=2):
        if (a * b ) % 10**18 == 0:
            print(a, b)
            ans += 1
    return ans

def main():
    N = read_int()
    A = [input() for _ in range(N)]
    print(slv(N, A))
    # print(ref(N, A))

    # N = 2 * 10**5
    # for _ in range(1000):
    #     A = []
    #     for _ in range(N):
    #         b = str(random.randint(1, 10)) + '.' + str(random.randint(0, 10**9))
    #         A.append(b)

    #     a = slv(N, A)
    #     # b = ref(N, A)
    #     # print(a, b)
    #     # if a != b:
    #     #     print(a, b)
    #     #     print(A)
    #     #     break



if __name__ == '__main__':
    main()