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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y


N = int(readline())
A = [None]*N
temp = read().split()
for i,s in enumerate(temp):
    s = s.decode().rstrip()
    if '.' in s:
        a,b = s.split('.')
        n = int(a+b)*10**(9-len(b))
    else:
        n = int(s)*10**9
    A[i] = n

def conv(n):
    c2 = 0
    while n%2 == 0:
        n //= 2
        c2 += 1
    c5 = 0
    while n%5 == 0:
        n //= 5
        c5 += 1
    return (c2,c5)

A = [conv(a) for a in A]
grid = [[0]*19 for _ in range(19)]

for x,y in A:
    grid[min2(x,18)][min2(y,18)] += 1

temp = [[0]*20 for _ in range(19)]
for i in range(19):
    c = 0
    for j in reversed(range(19)):
        c += grid[i][j]
        temp[i][j] = c

acc = [[0]*20 for _ in range(20)]

for j in range(20):
    c = 0
    for i in reversed(range(19)):
        c += temp[i][j]
        acc[i][j] = c

cnt = 0
for x,y in A:
    p,q = max2(0,18-x),max2(0,18-y)
    cnt += acc[p][q]
    if x*2 >= 18 and y*2 >= 18:
        cnt -= 1

print(cnt//2)

Solution (Python):
n = int(input())
a = []
howmany = [[0] * (19) for _ in range(19)]
for i in range(n):
    x = input()
    len_x = len(x)
    if '.' in x:
        idx = x.index('.')
        x = int(x.replace('.', '') + '0' * (9 - len_x + idx + 1))
    else:
        x = int(x)
        x = x * 10 ** 9
    
    cnt_2, cnt_5 = 0, 0
    while x % 2 == 0:
        x //= 2
        cnt_2 += 1
    while x % 5 == 0:
        x //= 5
        cnt_5 += 1
    cnt_2 = min(cnt_2, 18)
    cnt_5 = min(cnt_5, 18)
    howmany[cnt_2][cnt_5] += 1
    a.append((cnt_2, cnt_5))

for i in range(18, -1, -1):
    for j in range(18, 0, -1):
        howmany[i][j-1] += howmany[i][j]

for j in range(18, -1, -1):
    for i in range(18, 0, -1):
        howmany[i-1][j] += howmany[i][j]



cnt = 0
for i in range(n):
    l, r = a[i]
    if l >= 9 and r >= 9:
        cnt += howmany[18-l][18-r] - 1
    else:
        cnt += howmany[18-l][18-r]


print(cnt // 2)

Solution (Python):
n = int(input())
twos = [0]*n
fives = [0]*n


table = [[0 for _ in range(100)] for _ in range(100)]
table_acm = [[0 for _ in range(100)] for _ in range(100)]
offset = 20

def divisor(x,mod):
    ret = 0
    while True:
        if x % mod == 0:
            x //= mod
            ret+=1
        else:
            return ret

def factor(x):
    two = 0
    five = 0
    if '.' not in x:
        y = int(x)
        two = divisor(y,2)
        five = divisor(y,5)
    else:
        order = x.find('.')
        order = len(x) - 1 - order
        two = -order
        five = -order
        y = int(x.replace(".",""))
        two += divisor(y,2)
        five += divisor(y,5)
    return (two,five)

for i in range(n):
    x = input()
    two,five = factor(x)
    table[two+offset][five+offset] += 1
    table_acm[two+offset][five+offset] += 1

for i in range(99,0,-1):
    for j in range(99,0,-1):
        table_acm[i-1][j-1] = table_acm[i-1][j] + table_acm[i][j-1] - table_acm[i][j] + table[i-1][j-1]

ret = 0
for i in range(100):
    for j in range(100):
        ret += table[i][j] * table_acm[max(2*offset - i,0)][max(2*offset - j,0)]


print((ret-table_acm[offset][offset])//2)

Solution (Python):





constant = 10 ** 9

N = int(input())
numList = []
for _ in range(N):
    a = float(input())
    numList.append(round(constant * a))

ListTwoandFive = [] 
ListTwoandFivePartialSum = [] 

for i in range(19):
    ListTwoandFive.append([])
    ListTwoandFivePartialSum.append([])
    for j in range(19):
        ListTwoandFive[i].append(0)
        ListTwoandFivePartialSum[i].append(0)

for elem in numList:
    cnt2 = 0
    cnt5 = 0
    while elem % 2 == 0:
        elem //= 2
        cnt2 += 1
    while elem % 5 == 0:
        elem //= 5
        cnt5 += 1
    ListTwoandFive[min(cnt2,18)][min(cnt5,18)] += 1

for i in range(18,-1,-1):
    for j in range(18,-1,-1):
        if i == 18 and j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j]
        elif i == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i][j+1]
        elif j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j]
        else:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j] +\
                 ListTwoandFivePartialSum[i][j+1] - ListTwoandFivePartialSum[i+1][j+1]

cnt = 0

for i in range(19):
    for j in range(19):
        cnt += ListTwoandFive[i][j] * ListTwoandFivePartialSum[18 - i][18 - j]


cnt -=  ListTwoandFivePartialSum[9][9]
cnt //= 2

print(cnt)

Solution (Python):
n = int(input())
numbers = [[0] * 39 for _ in range(39)]
offset = 19
for _ in range(n):
    a = input()
    log2 = 0
    log5 = 0
    if '.' in a:
        b, c = a.split('.')
        log2 -= len(c)
        log5 -= len(c)
        d = int(b + c)
    else:
        d = int(a)
    while d % 2 == 0:
        d //= 2
        log2 += 1
    while d % 5 == 0:
        d //= 5
        log5 += 1
    log2 = min(log2, 19)
    numbers[log2 + offset][log5 + offset] += 1

acc = [[0] * 39 for _ in range(39)]

for i in range(37, -1, -1):
    acc[i][-1] = numbers[i][-1] + acc[i + 1][-1]

for j in range(37, -1, -1):
    acc[-1][j] = numbers[-1][j] + acc[-1][j + 1]

for i in range(37, -1, -1):
    for j in range(37, -1, -1):
        acc[i][j] = numbers[i][j] + acc[i + 1][j] + acc[i][j + 1] - acc[i + 1][j + 1]

ans = 0

for i in range(39):
    for j in range(39):
        if numbers[i][j] == 0:
            continue
        log2 = i - offset
        log5 = j - offset
        pi = -log2 + offset
        pj = -log5 + offset
        tmp = acc[pi][pj]
        if pi <= i and pj <= j:
            tmp -= 1
        ans += numbers[i][j] * tmp

ans //= 2
print(ans)

Solution (Python):
n=int(input())
data=[[0]*50 for i in range(50)]

for i in range(n):
    s=input()
    l=len(s)
    num=0
    sho=0
    keta=1
    for i in range(l):
        if(s[l-i-1]!='.'):
            num+=keta*int(s[l-i-1])
            keta*=10
        else:
            sho=i
    
    two=-sho
    five=-sho
    for i in range(100):
        if(num%2==0):
            two+=1
            num//=2
        else:
            break
    for i in range(100):
        if(num%5==0):
            five+=1
            num//=5
        else:
            break
    
    data[two+9][five+9]+=1


ans=0
for i in range(50):
    for j in range(50):
        jibun=data[i][j]
        if(jibun==0):
            continue
        aite=0
        for p in range(max(0,18-i),50):
            for q in range(max(0,18-j),50):
                aite+=data[p][q]
                if(p==i and j==q):
                    aite-=1
        ans+=jibun*aite
        

print(ans//2)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()
A = []
for _ in range(N):
    a = LS2()
    if not '.' in a:
        a = int(''.join(a))
        a *= 10**9
        b,c = 0,0
        while a % 2 == 0:
            a //= 2
            b += 1
        while a % 5 == 0:
            a //= 5
            c += 1
        A.append((b-9,c-9))
    else:
        i = a.index('.')
        l = len(a)
        del a[i]
        a += ['0']*(9-l+1+i)
        a = int(''.join(a))
        b, c = 0, 0
        while a % 2 == 0:
            a //= 2
            b += 1
        while a % 5 == 0:
            a //= 5
            c += 1
        A.append((b - 9, c - 9))


from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

ans = 0
for a in d.keys():
    b,c = a
    x = 0
    for e in d.keys():
        f,g = e
        if f >= -b and g >= -c:
            x += d[e]
    ans += d[a]*x

for a in d.keys():
    b,c = a
    if b >= 0 and c >= 0:
        ans -= d[a]

print(ans//2)

Solution (Python):
import sys
readline = sys.stdin.readline

G = 10**10
lai = 0
def Decimal(x):
    global lai
    a = x.strip().split('.')
    if len(a) == 1 or all([ai == '0' for ai in a[1]]):
        lai += 1
        return int(a[0])*G
        
    lf = len(a[1])
    i, f = map(int, a)
    return (i*10**(lf) + f)*10**(10-lf)
    
    
N = int(readline())
A = [Decimal(readline()) for _ in range(N)]

H = 200
geta = 100
Grid = [[0]*H for _ in range(H)]
i25 = []


for af in A:
    i2 = -10
    i5 = -10
    while af%2 == 0:
        af //= 2
        i2 += 1
    while af%5 == 0:
        af //= 5
        i5 += 1
    i25.append((i2, i5)) 


for i2, i5 in i25:
    Grid[geta+i2][geta+i5] += 1

for i in range(geta+90, geta-90, -1):
    for j in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i][j+1]

for j in range(geta+90, geta-90, -1):
    for i in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i+1][j]


ans = 0
for i2, i5 in i25:
    ans += Grid[geta-i2][geta-i5]
    
print((ans-lai)//2)

Solution (Python):
grid=[]
for i in range(19):
  grid.append([])
  for j in range(19):
    grid[-1].append(0)
n=int(input())
twos=[]
fives=[]
for i in range(n):
  t=input()
  predec=[]
  afdec=[]
  flag=0
  for j in range(len(t)):
    if t[j]=='.':
      flag=1
      continue
    if flag==0:
      predec.append(t[j])
    if flag==1:
      afdec.append(t[j])
  s=int(''.join(predec))*(10**9)
  if len(afdec)>0:
    s+=int(''.join(afdec))*(10**(9-len(afdec)))
  twos=0
  while s%2==0 and twos<18:
    twos+=1
    s=s//2
  fives=0
  while s%5==0 and fives<18:
    fives+=1
    s=s//5
  grid[twos][fives]+=1
ans=0
for i in range(19):
  for j in range(19):
    for k in range(18-i,19):
      for l in range(18-j,19):
        ans+=grid[i][j]*grid[k][l]
    if i>=9 and j>=9:
      ans-=grid[i][j]
print(ans//2)

Solution (Python):
from collections import defaultdict
N = int(input())

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

def get25(p):
  n2 = 0
  n5 = 0
  while p % 2 == 0:
    n2 += 1
    p //= 2
  while p % 5 == 0:
    n5 += 1
    p //= 5
  return (n2, n5)

d = defaultdict(int)

for i in range(N):
  s = input()
  for i, c in enumerate(s):
    if c == '.':
      q = int(s[:i] + s[i+1:])
      p = 10 ** (len(s) - i - 1)
      break
  else:
    q = int(s)
    p = 1
  g = gcd(p, q)
  p, q = p // g, q // g
  p2, p5 = get25(p)
  q2, q5 = get25(q)
  

  d[(q2 - p2, q5 - p5)] += 1
  



d = list(d.items())

ans = 0



for j in range(len(d)):
  if d[j][0][0] >= 0 and d[j][0][1] >= 0:
    ans += d[j][1] * (d[j][1] - 1) // 2
  for i in range(j):
    if d[i][0][0] + d[j][0][0] >= 0 and d[i][0][1] + d[j][0][1] >= 0:
      
      ans += d[i][1] * d[j][1]

print(ans)

Solution (Python):
N = int(input())
A = []
for i in range(N):
    X = input()
    if "." in X:
        XL = X.split(".")
        XN = len(XL[1])
        X = int(XL[0])*10**XN+int(XL[1])
        Y = X*10**(9-XN)
    else:
        Y = int(X)*10**9
    A.append(Y)
T = [[0]*2 for i in range(N)]
max2 = 0
max5 = 0
for i in range(N):

    X = A[i]
    cnt = 0
    while X%5==0:
        cnt+=1
        X = X//5
    T[i][0]=cnt
    max5 = max(max5,cnt)

    X = A[i]
    cnt = 0
    while X%2==0:
        cnt+=1
        X = X//2
    T[i][1]=cnt
    max2 = max(max2,cnt)

S = [[0]*(max2+1) for i in range(max5+1)]

for i in range(N):
    S[T[i][0]][T[i][1]]+=1

out = 0
for j1 in range(max2+1):
    for i1 in range(max5+1):
        for j2 in range(max2+1):
            for i2 in range(max5+1):
                X = S[i1][j1]
                Y = S[i2][j2]
                if i1+i2>=18 and j1+j2>=18:
                    if i1==i2 and j1==j2:
                        out += X*(X-1)
                    else:
                        out += X*Y
print(out//2)

Solution (Python):
from itertools import groupby
from operator import itemgetter
import sys
input = sys.stdin.readline
read = sys.stdin.read

N = int(input())
geta = 10**9
A = [int(round(float(input())*geta)) for _ in range(N)]
geta2 = geta * geta

B = []
for a in A:
    twoes = (a & -a).bit_length() - 1
    a >>= twoes
    fives = 0
    while a % 5 == 0:
        a //= 5
        fives += 1
    B.append((twoes, fives))

B.sort()

idx_r = N-1
Five = [0] * 19
ans = 0
for l2, group in groupby(B, key=itemgetter(0)):
    while idx_r >= 0:
        r2, r5 = B[idx_r]
        if r2 + l2 < 18:
            break
        Five[r5 if r5<=18 else 18] += 1
        idx_r -= 1
    
    for _, l5 in group:
        
        ans += sum(Five[(18-l5) if l5<=18 else 0:])
        if l2>=9 and l5>=9:
            ans -= 1
print(ans//2)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    A = []
    for _ in range(N):
        A.append(input().rstrip('\n'))

    TF = []
    for a in A:
        if "." not in a:
            t = f = 0
            a = int(a)
            while True:
                if a%2 == 0:
                    t += 1
                    a //= 2
                else:
                    break
            while True:
                if a%5 == 0:
                    f += 1
                    a //= 5
                else:
                    break
        else:
            a0, a1 = a.split(".")
            if int(a1) == 0:
                t = f = 0
                a0 = int(a0)
            else:
                a1 = [s for s in a1]
                while a1:
                    if a1[-1] == "0":
                        a1.pop()
                    else:
                        break
                a1 = "".join(a1)
                t = f = -len(a1)
                a0 = int("".join([a0, a1]))
            while True:
                if a0%2 == 0:
                    t += 1
                    a0 //= 2
                else:
                    break
            while True:
                if a0%5 == 0:
                    f += 1
                    a0 //= 5
                else:
                    break
        TF.append((t, f))

    Q = []
    for q in TF:
        t, f = q
        Q.append((t, f, 0))
        Q.append((-t, -f, 1))
    Q.sort(key=lambda x: x[2])
    Q.sort(key=lambda x: x[1], reverse=True)
    Q.sort(key=lambda x: x[0], reverse=True)
    bit = Bit(50)
    ans = 0
    for t, f, x in Q:
        if x == 0:
            bit.add(f+10, 1)
        else:
            ans += bit.sum(50) - bit.sum(f+10-1)
            if t <= 0 and f <= 0:
                ans -= 1
    print(ans // 2)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

N = int(input())

dic = {}
lis = [[0] * 19 for i in range(19)]
ans = 0

for loop in range(N):

    S = stdin.readline()
    S = S[:-1]

    if "." not in S:
        num = int(S) * (10**9)
    else:
        x,y = S.split(".")
        yy = int(y) * (10**(9-len(y)))
        xx = int(x) * 10**9
        num = xx+yy
    

    two = 0
    five = 0
    if num == 0:
        continue
    while num % 2 == 0:
        num //= 2
        two += 1
    while num % 5 == 0:
        num //= 5
        five += 1

    for i in range(19):
        for j in range(19):
            if i+two >= 18 and j+five>=18:
                ans += lis[i][j]
    lis[min(18,two)][min(18,five)] += 1
    

print (ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

n = int(readline())
data = read().split()
x = 10**9

a = []
for si in data:
    if('.' in si):
        num1,num2 = si.split('.')
        a.append(int(num1)*x + int(num2) * 10**(9- len(num2)))
    else:
        a.append(int(si) * x)

fac_25 = [[0]*19 for _ in range(19)]
for ai in a:
    

    num = 2
    cnt2 = 0
    while(ai%num == 0)&(cnt2<18):
        ai //= num
        cnt2 += 1

    num = 5
    cnt5 = 0
    while(ai%num == 0)&(cnt5<18):
        ai //= num
        cnt5 += 1

    fac_25[cnt2][cnt5] += 1

    

fac_cs = [[0]*19 for _ in range(19)]
for i in range(18,-1,-1):
    for j in range(18,-1,-1):
        fac_cs[i][j] = fac_25[i][j]
for i in range(18,-1,-1):
    for j in range(17,-1,-1):
        fac_cs[i][j] += fac_cs[i][j+1]

for i in range(17,-1,-1):
    for j in range(18,-1,-1):
        fac_cs[i][j] += fac_cs[i+1][j]

ans = 0
for i in range(18,-1,-1):
    for j in range(18,-1,-1):
        ans += fac_25[i][j] * fac_cs[18-i][18-j]


ans -= fac_cs[9][9]

ans //=2
print(ans)

Solution (Python):
N = int(input())
B = []
X = [[0]*19 for _ in range(19)]

for _ in range(N):
    s = input()
    if '.' not in s: s = s+'.0'
    a1, a2 = s.split('.')
    a2 = a2 + '0'*(9-len(a2))
    A = int(a1)*10**9 + int(a2)

    d2 = d5 = 0
    while A%2==0:
        A//=2
        d2+=1
    d2 = min(18, d2)

    while A%5==0:
        A//=5
        d5+=1
    d5 = min(18, d5)

    B.append((d2,d5))
    X[d2][d5] += 1

C = [[0]*19 for _ in range(19)]
for n2 in range(19):
    s = 0
    for n5 in range(18, -1, -1):
        s += X[n2][n5]
        C[n2][n5] = s

D = [[0]*19 for _ in range(19)]
for n5 in range(19):
    s = 0
    for n2 in range(18, -1, -1):
        s += C[n2][n5]
        D[n2][n5] = s

ans = 0
for n2, n5 in B:
    if n2*2>=18 and n5*2>=18: ans-=1
    ans += D[18-n2][18-n5]
    
print(ans//2)

Solution (Python):
N = int(input())
p2 = [0] * N
p5 = [0] * N

out = 0

for i in range(N):
    s = input()
    
    if '.' in s:
        a, b = s.split('.')
        inp = int(a+b)
        twos = -len(b)
        fives = -len(b)
    else:
        inp = int(s)
        twos = 0
        fives = 0

    while inp % 2 == 0:
        twos += 1
        inp //= 2
    while inp % 5 == 0:
        fives += 1
        inp //= 5

    if twos >= 0 and fives >= 0:
        out -= 1

    p2[i] = twos
    p5[i] = fives

count = [[0] * 105 for i in range(105)]
for i in range(N):
    count[p2[i]][p5[i]] += 1

pref = [[0] * 105 for i in range(105)]
for i in range(50,-51,-1):
    for j in range(50, -51, -1):
        curr = count[i][j]
        curr += pref[i + 1][j]
        curr += pref[i][j + 1]
        curr -= pref[i + 1][j + 1]
        pref[i][j] = curr

for i in range(N):
    out += pref[-p2[i]][-p5[i]]
    
print(out//2)

Solution (Python):



from fractions import *

n = int(input())

mp = dict()
for i in range(n):
    var = Fraction(input().strip())
    nom = var.numerator
    denom = var.denominator

    i, j = 0, 0
    
    while denom % 2 == 0:
        i -= 1
        denom //= 2
    
    while denom % 5 == 0:
        j -= 1
        denom //= 5

    while nom % 2 == 0:
        i += 1
        nom //= 2

    while nom % 5 == 0:
        j += 1
        nom //= 5

    i = min(i, 10)
    j = min(j, 10)

    mp[(i, j)] = mp.get((i, j), 0) + 1

ans = 0
for (a, cnt1) in mp.items():
    for (b, cnt2) in mp.items():
        if a < b and a[0] + b[0] >= 0 and a[1] + b[1] >= 0:
            ans += cnt1 * cnt2

for (a, cnt) in mp.items():
    if a[0] >= 0 and a[1] >= 0:
        ans += cnt * (cnt - 1) // 2
            
print(ans)

Solution (Python):
n = int(input())

num = {}
for i in range(n):
    a = input()
    if "." in a:
        temp = a.index(".")
        a1 = len(a) - temp - 1
        a = int(a[:temp] + a[temp + 1:])
    else:
        a1 = 0
        a = int(a)
    a_ = a
    a2 = 0
    for i in range(18):
        if a % 2 == 0:
            a2 += 1
            a //= 2
        else:
            break
    a3 = 0
    for i in range(18):
        if a_ % 5 == 0:
            a3 += 1
            a_ //= 5
        else:
            break
    num.setdefault((a1, a2, a3), 0)
    num[(a1, a2, a3)] += 1
num2 = []
for i, j in num.items():
    num2.append([i, j])
ans = 0
for i in range(len(num2)):
    for j in range(i, len(num2)):
        if i == j:
            temp = num2[i]
            if temp[0][0] <= min(temp[0][1], temp[0][2]):
                ans += temp[1] * (temp[1] - 1) // 2
        else:
            temp = num2[i]
            temp2 = num2[j]
            if temp[0][0] + temp2[0][0] <= min(temp[0][1] + temp2[0][1], temp[0][2] + temp2[0][2]):
                ans += temp[1] * temp2[1]
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

def calc(s):
    if "." not in s:
        n = int(s) * 10 ** 9
    else:
        s1, s2 = s.split(".")
        n = int(s1) * 10 ** 9 + int(s2) * 10 ** (9 - len(s2))
    
    a = 0
    b = 0
    while n % 2 == 0:
        n //= 2
        a += 1
    while n % 5 == 0:
        n //= 5
        b += 1
    return (min(a, 18), min(b, 18))

ans = 0
N = int(input())
X = [[0] * 19 for _ in range(19)]
for _ in range(N):
    a, b = calc(input())
    if a >= 9 and b >= 9:
        ans -= 1
    X[a][b] += 1

Y = [x[:] for x in X]

for i in range(18)[::-1]:
    for j in range(19):
        Y[i][j] += Y[i+1][j]
for i in range(19):
    for j in range(18)[::-1]:
        Y[i][j] += Y[i][j+1]

for i in range(19):
    for j in range(19):
        ans += X[i][j] * Y[18-i][18-j]
print(ans // 2)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

cnt25 = [[0]*19 for i in range(19)]

for i in range(n):
    a = input()[:-1]
    cnt2 = 0
    cnt5 = 0
    if "." in a:
        a, b = a.split(".")
        cnt2 += 9 - len(b)
        cnt5 += 9 - len(b)
        a = int(a+b)
    else:
        a = int(a)
        cnt2 += 9
        cnt5 += 9
    b = a
    while a>0 and a%2 == 0:
        a //= 2
        cnt2 += 1
    while b>0 and b%5 == 0:
        b //= 5
        cnt5 += 1

    cnt25[min(18, cnt2)][min(18, cnt5)] += 1

sumcnt = [[cnt25[i][j] for j in range(19)] for i in range(19)]
for i in range(18,-1,-1):
    for j in range(18, 0, -1):
        sumcnt[i][j-1] += sumcnt[i][j]

for i in range(18, -1, -1):
    for j in range(18, 0, -1):
        sumcnt[j-1][i] += sumcnt[j][i]

ans = 0
for i in range(19):
    for j in range(19):
        ans += cnt25[i][j] * sumcnt[18-i][18-j]
        if 18-i <= i and 18-j <= j and cnt25[i][j] > 0:
            ans -= cnt25[i][j]


print(ans//2)

Solution (Python):
N = int(input())
A = [input() for _ in range(N)]

from collections import Counter
ctr = Counter()

for a in A:
    of = 0
    if '.' in a:
        of = a[::-1].index('.')
        a = a.replace('.', '')
    a = int(a)
    ni = go = -of
    while a%2==0:
        a//=2
        ni += 1
    while a%5==0:
        a//=5
        go += 1
    ctr[(ni,go)] += 1

ans = 0
for (ni1,go1),v1 in ctr.items():
    for (ni2,go2),v2 in ctr.items():
        if ni1+ni2 < 0 or go1+go2 < 0: continue
        if ni1==ni2 and go1==go2:
            ans += v1*(v1-1)
        else:
            ans += v1*v2
print(ans//2)

Solution (Python):


from collections import defaultdict
N = int(input())
A = []
for i in range(N):
    x = float(input())
    x = "{:.9f}".format(x)
    x=int(x[:-10]+x[-9:])
    A.append(x)
remove = 0
for i in range(N):
    if (A[i]**2) % (10**18) == 0:
        remove += 1
D = defaultdict(int)
data = []
for x in A:
    order2 = 0
    order5 = 0
    K = x
    while K % 2 == 0:
        order2 += 1
        K = K//2
    while K % 5 == 0:
        order5 += 1
        K = K//5
    data.append((order2, order5))
    for i in range(order2+1):
        for j in range(order5+1):
            D[2**i*5**j] += 1
ans = 0
for ord2, ord5 in data:
    new_ord2 = max(0, 18-ord2)
    new_ord5 = max(0, 18-ord5)
    ans += D[(2**new_ord2)*(5**new_ord5)]
ans-=remove
ans = ans//2
print(ans)

Solution (Python):
n = int(input())
d = [[0] * 21 for _ in range(21)]
ans = 0
for _ in range(n):
    a = input()
    if '.' not in a:
        c2 = c5 = 0
    else:
        c2 = c5 = -(len(a) - (a.index('.') + 1))
    a = int(a.replace('.',''))
    while a % 2 == 0:
        a //= 2
        c2 += 1
    while a % 5 == 0:
        a //= 5
        c5 += 1
    c2 = min(10, c2)
    c5 = min(10, c5)
    for i in range(-c2, 11):
        for j in range(-c5, 11):
            ans += d[i+10][j+10]
    d[c2+10][c5+10] += 1
print(ans)

Solution (Python):
N = int(input())

two_fives = []
mapping = [[0] * 19 for _ in range(19)]
ans = 0
for _ in range(N):
    s = input()
    if '.' in s:
        m, x = s.split('.')
        A = int(m) * 10 ** 9 + int(x.ljust(9, '0'))
    else:
        A = int(s) * 10 ** 9

    for two in range(19):
        if A % 2 == 0:
            A //= 2
        else:
            break
    for five in range(19):
        if A % 5 == 0:
            A //= 5
        else:
            break
        
    two_fives.append((two, five))
    mapping[18 - two][18 - five] += 1
    if two >= 9 and five >= 9:
        ans -= 1 

for i in range(18):
    for j in range(19):
        mapping[i+1][j] += mapping[i][j]

for i in range(19):
    for j in range(18):
        mapping[i][j+1] += mapping[i][j]


for two, five in two_fives:
    ans += mapping[two][five]


ans //= 2
print(ans)

Solution (Python):
from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n = int(input())
da = [[0 for i in range(50)] for j in range(50)]
ans = 0
for i in range(n):
    now = round(float(input())*1000000000)
    
    a, b = 0, 0
    while(now%5 == 0):
        now //= 5
        a += 1
    while(now%2 == 0):
        now //= 2
        b += 1
    da[a][b] += 1
    
    if a >= 9 and b >= 9: ans -= 1


for i in range(50):
    for j in range(50):
        for k in range(50):
            for l in range(50):
                if i+k >= 18 and j+l>= 18:
                    ans += da[i][j]*da[k][l]

print(ans//2)

Solution (Python):
from fractions import Fraction
N=int(input())
A=[Fraction(input()) for i in range(N)]
def vp(n,p):
    res=0
    m=n
    while(m>0):
        if m%p==0:
            res+=1
            m//=p
        else:
            return res
def div25(f):
    return (vp(f.numerator,2)-vp(f.denominator,2),vp(f.numerator,5)-vp(f.denominator,5))
B=[div25(f) for f in A]
B.sort()
MAX_N=100
C=[[0 for j in range(MAX_N)] for i in range(MAX_N)]
for seq in B:
    x,y=seq
    C[x+MAX_N//2][y+MAX_N//2]+=1
D=[[0 for j in range(MAX_N)] for i in range(MAX_N+1)]
E=[[0 for j in range(MAX_N+1)] for i in range(MAX_N+1)]
for i in range(MAX_N):
    for j in range(MAX_N):
        D[i+1][j]=D[i][j]+C[i][j]
for i in range(MAX_N+1):
    for j in range(MAX_N):
        E[i][j+1]=E[i][j]+D[i][j]
ans=0
for seq in B:
    x,y=seq
    tmp=E[MAX_N][MAX_N]+E[-x+MAX_N//2][-y+MAX_N//2]-E[MAX_N][-y+MAX_N//2]-E[-x+MAX_N//2][MAX_N]
    if x>=0 and y>=0:
        ans+=tmp-1
    else:
        ans+=tmp
print(ans//2)

Solution (Python):


n = int(input())
A = [input() for i in range(n)]
B = []

for i in range(n):
    if "." in A[i]:
        ind = A[i].index(".")
        A[i] += "0" * (10-(len(A[i]) - ind))
        B.append(int(A[i][:ind] + A[i][ind+1:]))
    else:
        B.append(int(A[i] + "0" * 9))



l = 100
D = [[0] * l for i in range(l)]
E = []

for i in range(n):
    a2 = 0
    a5 = 0
    while B[i] % 2 == 0:
        a2 += 1
        B[i] //= 2
    while B[i] % 5 == 0:
        a5 += 1
        B[i] //= 5
    D[a2][a5] += 1
    E.append([a2,a5])

for i in range(l-2,-1,-1):
    D[l-1][i] += D[l-1][i+1]
for i in range(l-2,-1,-1):
    D[i][l-1] += D[i+1][l-1]

for i in range(l-2,-1,-1):
    for j in range(l-2,-1,-1):
        D[i][j] += D[i+1][j] + D[i][j+1] - D[i+1][j+1]



ans = 0
for i in range(n):
    b2 = max(0, 18-E[i][0])
    b5 = max(0, 18-E[i][1])
    ans += D[b2][b5]
    if E[i][0]>=b2 and E[i][1]>=b5:
        ans -= 1

print(ans//2)

Solution (Python):
def main():
    n = int(input())
    a = [input() for _ in [0]*n]
    b = []
    for i in a:
        j = i.find(".")
        if j == -1:
            b.append(int(i)*10**9)
        else:
            k = 10-len(i)+j
            i = i.replace(".", "")
            b.append(int(i)*10**k)
    d = dict()
    for i in b:
        cnt_a = 0
        while(True):
            if i % 2 != 0:
                break
            cnt_a += 1
            i //= 2
        cnt_b = 0
        while(True):
            if i % 5 != 0:
                break
            cnt_b += 1
            i //= 5
        if (cnt_a, cnt_b) in d:
            d[(cnt_a, cnt_b)] += 1
        else:
            d[(cnt_a, cnt_b)] = 1
    ans = 0
    for i in range(50):
        for j in range(20):
            if (i, j) not in d:
                continue
            temp1 = d[(i, j)]
            for k in range(50):
                for l in range(20):
                    if (k, l) not in d:
                        continue
                    temp2 = d[(k, l)]
                    if i+k >= 18 and j+l >= 18:
                        if i == k and j == l:
                            ans += temp1*(temp2-1)
                        else:
                            ans += temp1*temp2

    print(ans//2)


main()

Solution (Python):
import sys
input = sys.stdin.readline

class BIT2D:
    def __init__(self, H, W):
        self.H = H
        self.W = W
        self.data = [[0] * (H+1) for _ in range(W+1)]

    def add(self, a, b, x):
        a += 1
        b += 1
        i = a
        while i <= self.H:
            j = b
            while j <= self.W:
                self.data[i][j] += x
                j += j & -j
            i += i & -i

    def sum(self, a, b):
        a += 1
        b += 1
        ret = 0
        i = a
        while i > 0:
            j = b
            while j > 0:
                ret += self.data[i][j]
                j -= j & -j
            i -= i & -i
        return ret

N = int(input())
A = []
for _ in range(N):
    n = input().rstrip()
    if '.' not in n:
        A.append(int(n) * 10**9)
    else:
        a, b = n.split('.')
        b += '0' * (9 - len(b))
        A.append(int(a + b))
ans = 0
bit = BIT2D(100, 100)
for i in range(N):
    cnt2 = cnt5 = 0
    while A[i] % 2 == 0:
        A[i] //= 2
        cnt2 += 1
    while A[i] % 5 == 0:
        A[i] //= 5
        cnt5 += 1
    if cnt2 >= 18 and cnt5 >= 18:
        ans += i
    else:
        ans += i - bit.sum(99, 17 - cnt5) - bit.sum(17 - cnt2, 99) + bit.sum(17 - cnt2, 17 - cnt5)
    bit.add(cnt2, cnt5, 1)
print(ans)