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: Accepted

Solution code:
def fact2(a, b):
    c2 = 0
    c5 = 0
    while a%2 == 0:
        a //= 2
        c2 += 1
    while a%5 == 0:
        a //= 5
        c5 += 1
    return min(c2-b, 9), min(c5-b,9)

def main():
    N = int( input())
    A2 = [0]*N
    A5 = [0]*N
    AS = [0]*N
    for i in range(N):
        a = input()
        if '.' in a:
            b, c = a.split('.')
            if int(c) == 0:
                pass
            else:
                AS[i] = len(c)
                b += c
        else:
            b = a
        # A2[i], A5[i] = fact( int(b))
        # print(b)
        A2[i], A5[i] = fact2( int(b), AS[i])

    R = [ [0]*19 for _ in range(19)]
    for i in range(N):
        a, b = A5[i]+9, A2[i]+9
        R[a][b] += 1
    AR = [ [0]*19 for _ in range(19)]
    for i in range(18,-1,-1):
        for j in range(17,-1,-1):
            R[i][j] = R[i][j] + R[i][j+1]
    for j in range(19):
        for i in range(17,-1,-1):
            R[i][j] += R[i+1][j]
    ans = 0
    # print("\n".join( [" ".join( map( str, a)) for a in AR]))
    for k in range(N):
        i, j = A5[k], A2[k]
        if i <= 9 and j <= 9:
            ans += R[-i+9][-j+9]
            # print(-i+9,-j+9)
        if AS[k] == 0:
            ans -= 1
    print(ans//2)

# 2
# 10.73741824 
# 3051.7578125
# 2**30, 2**15

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

def main():
    n = int(input())
    a = [None]*n
    for i in range(n):
        sub = input().replace("\n", "")
        if "." in sub:
            x, y = map(str, sub.split("."))
            s = int(x)*1000000000+10**(9-len(y))*int(y)
        else:
            s = int(sub)
            s *= 1000000000
        a[i] = divide(s)

    dp = [[0]*100 for _ in range(100)]
    for i in range(n):
        c1, c2 = a[i]
        dp[c1][c2] += 1
    
    for i in range(98, -1, -1):
        for j in range(98, -1, -1):
            dp[i][j] += dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]

    ans = 0
    for i in range(n):
        c1, c2 = a[i]
        if (c1 >= 9 and c2 >= 9):
            ans -= 1
        if c1 >= 18 and c2 >= 18:
            ans += dp[0][0]
            continue
        if c1 >= 18:
            ans += dp[0][18-c2]
            continue
        if c2 >= 18:
            ans += dp[18-c1][0]
            continue
        ans += dp[18-c1][18-c2]
        
    print(ans//2)
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math
from decimal import Decimal
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN, ROUND_DOWN

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''



def main():
    start = time.time()

    n = get_int()
    #youso2 = []
    #youso5 = []
    youso = []
    aite = [[0] * 20 for i in range(20)]

    ans = 0
    for i in range(0,n):
        s = input()
        wk = Decimal(s)
        wk = wk - wk.quantize(Decimal('0'), rounding=ROUND_DOWN)
        seisu = Decimal.is_zero(wk)

        if seisu:
            if '.' in s:
                s_i, s_d = s.split('.')
                s = s_i

            count2 = 0
            wk = int(s)
            for ii in range(0, 19):
                if wk % 2 == 0:
                    count2 += 1
                    wk = wk // 2
                else:
                    break

            count5 = 0
            wk = int(s)
            for ii in range(0, 19):
                if wk % 5 == 0:
                    count5 += 1
                    wk = wk // 5
                else:
                    break

            count5 = min(9, count5)
            count2 = min(9, count2)
            #youso.append([count2, count5])

        else:
            s_i, s_d = s.split('.')

            while s_d[-1] == '0':
                s_d = s_d[:-1]

            count2 = 0
            wk = int(s_i + s_d)
            for ii in range(0, 19):
                if (wk * 2) % 10 == 0:
                    wk = wk * 2 / 10
                    count2 += 1
                else:
                    break

            count5 = 0
            wk = int(s_i + s_d)
            for ii in range(0,19):
                if (wk * 5) % 10 == 0:
                    wk = wk * 5 / 10
                    count5 += 1
                else:
                    break

            count2_wk = -len(s_d) + count5
            count5 = min(9, -len(s_d) + count2)
            count2 = min(9, count2_wk)
            #youso.append([-len(s_d) + count5, -len(s_d) + count2])

        youso.append([count2, count5])
        aite[10 - count2][10 - count5] += 1
        #for ii in range (10 - count2, 20):
        #    for iii in range(10 - count5, 20):
        #        aite[ii][iii] += 1


    #print(time.time() - start)

    aite2 = [[0] * 20 for i in range(20)]
    for i in range (0,20):
        for ii in range (0, 20):
            for iii in range(i, 20):
                for iiii in range(ii, 20):
                    aite2[iii][iiii] += aite[i][ii]

    #print(time.time() - start)
    #print(youso)

    #for i in range(len(aite2)):
    #    print(i, aite2[i])

    ans = 0
    for i in range(0,n):
        y1 = youso[i]
        if y1[0] >= 0 and y1[1] >= 0:
            ans += aite2[10 + y1[0]][10 + y1[1]] -1
        else:
            ans += aite2[10 + y1[0]][10 + y1[1]]

    ans = ans // 2

    print(ans)
    #print(time.time() - start)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def divide(n, p):
    c = 0
    while n%p == 0 and c < 18:
        c += 1
        n //= p
    return c

n = int(input())
table = [[0]*19 for _ in range(19)]
for i in range(n):
    sub = input()
    key = float(sub)
    if "." in sub:
        a, b = map(str, sub.split("."))
        s = int(a)*1000000000+10**(9-len(b))*int(b)
    else:
        s = int(sub)
        s *= 1000000000
    if key != s/1000000000:
        while True:
            pass
    c2, c5 = divide(s, 2), divide(s, 5)
    table[c2][c5] += 1

ans = 0
for i in range(19):
    for j in range(19):
        for k in range(19):
            for l in range(19):
                if i+k < 18 or j+l < 18:
                    continue;
                if i == k and j == l:
                    ans += table[i][j]*(table[k][l]-1)
                else:
                    ans += table[i][j]*table[k][l]

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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))
cnt = defaultdict(int)
ans = 0
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
    cnt[(cnt2, cnt5)] += 1
for p1, c1 in cnt.items():
    for p2, c2 in cnt.items():
        if p1 > p2:
            continue
        if p1[0] + p2[0] >= 18 and p1[1] + p2[1] >= 18:
            if p1 == p2:
                ans += c1 * (c1 - 1) // 2
            else:
                ans += c1 * c2
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
p=[[0]*51 for _ in range(51)]
for _ in range(n):
    a=float(input())
    a*=10**9
    a=round(a)
    cnt2,cnt5=0,0
    while a%2==0:
        a//=2
        cnt2+=1
    while a%5==0:
        a//=5
        cnt5+=1
    p[cnt2][cnt5]+=1
ans=0
for i in range(51):
    for j in range(51):
        for k in range(51):
            for l in range(51):
                if k>=18-i and l>=18-j:
                    if i==k and j==l:
                        ans+=p[i][j]*(p[i][j]-1)
                    else:
                        ans+=p[i][j]*p[k][l]
print(ans//2)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
MAX = 10 ** 9
d = defaultdict(int)
for i in range(N):
    a = round(float(input()) * MAX)
    two = 0
    while a % 2 == 0:
        two += 1
        a //= 2
    five = 0
    while a % 5 == 0:
        five += 1
        a //= 5
    d[(two, five)] += 1

ans = 0
for p1 in d.keys():
    for p2 in d.keys():
        if (p1[0] + p2[0] >= 18) and (p1[1] + p2[1] >= 18):
            if p1 < p2:
                ans += d[p1] * d[p2]
            elif p1 == p2:
                ans += d[p1] * (d[p1] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from decimal import *
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
div=[[0]*19 for _ in range(19)]
ans=0
for _ in range(N):
    x=int(Decimal(input())*10**9)
    two,five=0,0
    while x%2==0 and two<18:
        two+=1
        x//=2
    while x%5==0 and five<18:
        five+=1
        x//=5
    ans+=div[18-two][18-five]
    for i in range(two+1):
        for j in range(five+1):
            div[i][j]+=1
print(ans)

Submission status: Accepted

Solution code:
def solve(n, a_str_list):

    count_25 = [[0] * 19 for _ in range(19)]
    for i in range(n):
        a_str = a_str_list[i]
        if "." in a_str:
            a_str_a, a_str_b = a_str.split(".")
            a_int = int(a_str_a + a_str_b + "0" * (9 - len(a_str_b)))
        else:
            a_int = int(a_str) * 1000000000
        count_2 = 0
        count_5 = 0
        while a_int % 2 == 0:
            a_int = a_int // 2
            count_2 += 1
        while a_int % 5 == 0:
            a_int = a_int // 5
            count_5 += 1
        count_2 = min(count_2, 18)
        count_5 = min(count_5, 18)
        # print(a_str, count_2, count_5)
        count_25[count_2][count_5] += 1
    # print(count_25)

    res = 0
    for i0 in range(19):
        for j0 in range(19):
            for i1 in range(19):
                for j1 in range(19):
                    if count_25[i0][j0] * count_25[i1][j1] and i0 + i1 >= 18 and j0 + j1 >= 18:
                        # print(i0, j0, i1, j1)
                        if i0 == i1 and j0 == j1:
                            res += (count_25[i0][j0] - 1) * count_25[i0][j0]
                        elif i0 == i1:
                            res += count_25[i0][j0] * count_25[i0][j1]
                        elif j0 == j1:
                            res += count_25[i0][j0] * count_25[i1][j0]
                        else:
                            res += count_25[i0][j0] * count_25[i1][j1]
    # print(res)
    return res // 2


def main():
    n = int(input())
    a_str_list = [input() for _ in range(n)]
    res = solve(n, a_str_list)
    print(res)


def test():
    assert solve(5, ["7.5", "2.4", "17.000000001", "17", "16.000000000"]) == 3
    assert solve(11, [
        "0.9", "1", "1", "1.25", "2.30000", "5", "70", "0.000000001", "9999.999999999", "0.999999999", "1.000000001"
    ]) == 8


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

n=int(input())
z=[]
d=defaultdict(int)
for i in range(n):
    s=input()
    if '.' in s:
        ind=s.index('.')
        ls=len(s)
        p=ls-ind-1
        s=s[:ind]+s[ind+1:]
        s=int(s)
        c=gcd(s,10**p)
        s//=c
        t=(10**p)//c
    else:
        s=int(s)
        t=1
    l=[]
    for j in [s,t]:
        n2=0
        n5=0
        while j%2==0:
            n2+=1
            j//= 2
        while j%5==0:
            n5+=1
            j//= 5
        l.append([n2,n5])
    d[(l[0][0]-l[1][0],l[0][1]-l[1][1])]+=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)

Submission status: Accepted

Solution code:
import numpy as np
from decimal import Decimal
n=int(input())
q=np.zeros((19,19),"i8")
p=0
def f(x,y):
    d=0
    while x%y==0 and d<18:
        x//=y
        d+=1
    return d
for i in range(n):
    a=int(10**9*Decimal(input()))
    s,t=f(a,2),f(a,5)
    p+=q[18-s][18-t]
    q[:s+1,:t+1]+=1
print(p)

Submission status: Accepted

Solution code:
N = int(input())
M = 10
L = 2*M
A = [[0 for _ in range(L+1)] for _ in range(L+1)]

for _ in range(N):
  y = float(input())
  x = y
  x *= 10.**M
  x = int(x+0.1)
  k_2 = 0
  while x % 2 == 0 and k_2 < 2*M:
    x = x // 2
    k_2 += 1
  k_5 = 0 
  while x % 5 == 0 and k_5 < 2*M:
    x = x // 5
    k_5 += 1
  A[k_2][k_5] += 1

ans = 0
for k_2 in range(L+1):
  for k_5 in range(L+1):
    for l_2 in range(k_2, L+1):
      for l_5 in range(L+1):
        if k_2+l_2 >= 2*M and k_5+l_5 >= 2*M:
          if k_2 == l_2 and k_5 == l_5:
            ans += A[k_2][k_5]*(A[k_2][k_5]-1)//2
          elif l_2 > k_2 or (k_2 == l_2 and k_5 < l_5):
            ans += A[k_2][k_5]*A[l_2][l_5]          
#print(A)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
numbers = [[0] * 19 for _ in range(19)]
offset = 9
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, 9)
    log5 = min(log5, 9)
    numbers[log2 + offset][log5 + offset] += 1

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

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

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

for i in range(17, -1, -1):
    for j in range(17, -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(19):
    for j in range(19):
        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)

Submission status: Accepted

Solution code:
import sys
N = int(input())
acc = [[0]*19 for _ in range(19)]
a = []

for num in (sys.stdin.readline() for _ in range(N)):
    num = num.rstrip()
    idx = num.find(".")
    mul = 10**(9 if idx == -1 else 9 - (len(num) - idx - 1))
    n = int(num.replace(".", "")) * mul

    cnt2, cnt5 = 0, 0
    while n & 1 == 0:
        cnt2 += 1
        n >>= 1
    while n % 5 == 0:
        cnt5 += 1
        n /= 5

    acc[min(18, cnt2)][min(18, cnt5)] += 1
    a.append((min(18, cnt2), min(18, cnt5)))

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

ans = 0
for i, j in a:
    ans += acc[18-i][18-j] - (1 if i >= 9 and j >= 9 else 0)

print(ans // 2)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
B = [[0]*19 for x in range(19)]
C = [0]*N
D = [0]*N
a,b,c,d,e,ans = 0,['0']*9,0,0,0,0
for i in range(N):
    c = (input()+'.0').split('.')
    b = ['0']*9
    for k,v in enumerate(c[1]):
        b[k] = v
    A[i] = int(c[0]+''.join(b))

# print(*A)

for i in range(N):
    d,e = 0,0
    while (A[i] % 2 == 0) and (d < 18):
        A[i] //= 2
        d += 1
    while (A[i] % 5 == 0) and (e < 18):
        A[i] //= 5
        e += 1
    C[i] = d
    D[i] = e
    B[d][e] += 1

for i in range(N):
    c = C[i]
    d = D[i]
    B[c][d] -= 1
    for j in range(18-c,19):
        for k in range(18-d,19):
            ans += B[j][k]

print(ans)

Submission status: Accepted

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 (min2(cnt1,18), min2(cnt2,18))

def min2(x,y):
    return x if x < y else y

import sys
input = sys.stdin.readline

N = int(input())
F = []
for i in range(N):
    A = input().rstrip()
    if '.' in A:
        a,b = A.split('.')
        n = int(a+b)*10**(9-len(b))
    else:
        n = int(A) * 10 ** 9
    F.append(five(n))

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

print(temp)

Submission status: Accepted

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 (min2(cnt1,18), min2(cnt2,18))

def min2(x,y):
    return x if x < y else y

import sys
input = sys.stdin.readline

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

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

print(temp)

Submission status: Accepted

Solution code:
from collections import defaultdict
from decimal import Decimal
N = int(input())
T = defaultdict(int)
a = 0
b = 0
for i in range(N):
    A = Decimal((input()))
    A *= 10**9
    A = int(A)
    t = 0
    f = 0
    while(True):
        if A % 2 != 0:
            break
        A = A // 2
        t += 1
    while (True):
        if A % 5 != 0:
            break
        A = A // 5
        f += 1
    T[(t, f)] += 1
    a = max(a, t)
    b = max(b, f)

ans = 0
for k, v in T.items():
    for i in range(18-k[0], a+1):
        for j in range(18-k[1], b+1):
            if (i, j) in T:
                if k[0] == i and k[1] == j:
                    ans += v * (v-1)
                else:
                    ans += v * T[(i, j)]
print(ans//2)

Submission status: Accepted

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 (min(cnt1,18), min(cnt2,18))

N = int(input())

F = []
for i in range(N):
    A = float(input())
    A = round(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, temp)

print(temp)

"""
5
1
1
1
1
1
"""

Submission status: Accepted

Solution code:
n=int(input())
from decimal import Decimal as D
# A=[]
excel=[[0]*20 for i in range(50)]
query=[]
for i in range(n):
    q=input()
    q=D(q)
    q=int(q*10**9)
    num2=0 ;num5=0
    k=q
    for i in range(50):
        if k%2==0:
            k//=2
            num2+=1
        else:break
    k=q
    for i in range(20):
        if k%5==0:
            k//=5
            num5+=1
        else:break
    excel[num2][num5]+=1
    query.append([max(0,18-num2),max(0,18-num5)])

A=[[0] * 20 for i in range(50)] #累積和
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i==49 and j==19:
            A[i][j]=excel[i][j]
        elif i==49:
            A[i][j]=A[i][j+1]+excel[i][j]
        elif j==19:
            A[i][j]=A[i+1][j] + excel[i][j]
        else:
            A[i][j]=excel[i][j]+ A[i+1][j]+A[i][j+1]-A[i+1][j+1]

ans=0
for l in query:
    num2,num5=l
    if num2<=9 and num5<=9:
        ans+=A[num2][num5]-1
    else:
        ans+=A[num2][num5]

#for i in range(50):
 #   print(excel[:][i] , A[:][i])
print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
al = []

for _ in range(n):
    s = input()
    if '.' not in s:
        a = int(s)*(10**9)
        al.append(a)
    else:
        syousu = s.split('.')[1]
        rem0 = 9 - len(syousu)
        a = int(s.replace('.',''))*(10**rem0)
        al.append(a)

ans = 0
two_five_cnts = {}
for i in range(19):
    for j in range(19):
        two_five_cnts[(i,j)] = 0

for a in al:
    num = a
    two = 0
    five = 0
    for i in range(18):
        if num%2 == 0:
            num = num//2
            two += 1
        else:
            break
    for i in range(18):
        if num%5 == 0:
            num = num//5
            five += 1
        else:
            break
    
    for i in range(18-two,19):
        for j in range(18-five,19):
            ans += two_five_cnts[(i,j)]
    two_five_cnts[(two,five)] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [input() for _ in [0]*N]

for i,a in enumerate(A):
    b = a.split(".")
    if len(b)==1:
        A[i] = int(a)*10**9
        continue
    c = b[1]
    n = len(c)
    c += "0"*(9-n)
    A[i] = int(b[0] + c)

cnt = [[0]*20 for _ in [0]*20]
B = [(0,0)]*N
for k,a in enumerate(A):
    i = 0
    j = 0
    while a%2==0:
        a//=2
        i+=1
    while a%5==0:
        a//=5
        j+=1
    i = min(19,i)
    j = min(19,j)
    B[k] = (i,j)
    cnt[i][j] += 1

for i in range(1,20):
    i = 19-i
    for j in range(20):
        j = 19-j
        cnt[i][j] += cnt[i+1][j]

for i in range(20):
    i = 19-i
    for j in range(1,20):
        j = 19-j
        cnt[i][j] += cnt[i][j+1]

ans = 0
for i,j in B:
    me = int(i>=9 and j>=9)
    ans += cnt[max(0,18-i)][max(0,18-j)]-me

print(ans//2)

Submission status: Accepted

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

def calc(x):
    n = int(x * 10 ** 9 + 0.5)
    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(float(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)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    C = Counter()
    for _ in range(n):
        S = input()
        if '.' in S:
            a, b = S.split('.')
            a = int(a + b + '0' * (9 - len(b)))
        else:
            a = int(S + '0' * 9)
        two = five = 0
        while a % 2 == 0:
            two += 1
            a //= 2
        while a % 5 == 0:
            five += 1
            a //= 5
        C[two, five] += 1

    ans = 0
    for key0, val0 in C.items():
        i0, j0 = key0
        for key1, val1 in C.items():
            i1, j1 = key1
            if i0 + i1 >= 18 and j0 + j1 >= 18:
                if key0 == key1:
                    ans += val0 * (val0 - 1) // 2
                elif key0 < key1:
                    ans += val0 * val1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = [input() for _ in [0]*N]

for i,a in enumerate(A):
    b = a.split(".")
    if len(b)==1:
        A[i] = int(a)*10**9
        continue
    c = b[1]
    n = len(c)
    c += "0"*(9-n)
    A[i] = int(b[0] + c)

cnt = [[0]*50 for _ in [0]*50]
B = [(0,0)]*N
for k,a in enumerate(A):
    i = 0
    j = 0
    while a%2==0:
        a//=2
        i+=1
    while a%5==0:
        a//=5
        j+=1
    B[k] = (i,j)
    cnt[i][j] += 1

for i in range(1,50):
    i = 49-i
    for j in range(50):
        j = 49-j
        cnt[i][j] += cnt[i+1][j]

for i in range(50):
    i = 49-i
    for j in range(1,50):
        j = 49-j
        cnt[i][j] += cnt[i][j+1]

ans = 0
for i,j in B:
    me = int(i>=9 and j>=9)
    ans += cnt[max(0,18-i)][max(0,18-j)]-me

print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
twofive = defaultdict(int)
for i in range(N):
    a = round(float(input()) * (10**9))
    b = 0
    c = 0
    while a % 2 == 0 and b < 18:
        b += 1
        a //= 2
    while a % 5 == 0 and c < 18:
        c += 1
        a //= 5
    twofive[(b, c)] += 1
ans = 0
for b, c in twofive.keys():
    for d, e in twofive.keys():
        if b + d >= 18 and c + e >= 18:
            if (b, c) != (d, e):
                ans += twofive[(b, c)] * twofive[(d, e)]
            else:
                ans += twofive[(b, c)] * (twofive[(b, c)] - 1)
print(ans//2)

Submission status: Accepted

Solution code:
N = int(input())
A = []
C2 = [0] * N
C5 = [0] * N

P = 1000000000
for i in range(N):
    tmp = input().split(".")
    if len(tmp) == 2:
        a = int(tmp[1])
        for j in range(9-len(tmp[1])):
            a *= 10
        A.append(int(tmp[0]) * P + a)
    else:
        A.append(int(tmp[0]) * P)

for i in range(N):
    tmpp = A[i]
    tmp2 = A[i]
    while tmpp > 0:
        if tmpp % 2 == 0:
            tmpp //= 2
            C2[i] += 1
        else:
            break
    while tmp2 > 0:
        if tmp2 % 5 == 0:
            tmp2 //= 5
            C5[i] += 1
        else:
            break

Cc = [[0] * 19 for _ in range(19)]

for i in range(N):
    Cc[min(18, C2[i])][min(18, C5[i])]+=1

ans = 0
for i in range(N):
    if C2[i] >= 9 and C5[i] >= 9:
        ans -= 1
    l2 = max(0, 18 - C2[i])
    l5 = max(0, 18 - C5[i])
    for j in range(l2, 19):
        for k in range(l5, 19):
            ans += Cc[j][k]

print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())

lst = [[0 for _ in range(25)] for _ in range(25)]
int_cnt = 0
for _ in range(n):
    a = input()
    if "." in a:
        pos = a.index(".")
        a1, a2 = a[:pos], a[pos + 1:]
        l = len(a2)
        a = a1 + a2
        a = int(a)
        a *= 10 ** (9 - l)
    else:
        a = int(a)
        int_cnt += 1
        a *= 10 ** 9
    t = 0
    while a % 2 == 0:
        t += 1
        a //= 2
    f = 0
    while a % 5 == 0:
        f += 1
        a //= 5
    t = min(t, 24)
    f = min(f, 24)
    lst[t][f] += 1


 
ans = 0
for i in range(25):
    for j in range(25):
        for k in range(25):
            for l in range(25):
                if i + j >= 18 and k + l >= 18:
                    if i == j and k == l:
                        tmp = lst[i][k]
                        ans += tmp * (tmp - 1)
                    else:
                        ans += lst[i][k] * lst[j][l]
print(ans // 2)

Submission status: Accepted

Solution code:
import pprint
from collections import deque
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=list(input())
    #print(n)
    cnt=9
    d=deque()
    flag=1
    for i in range(len(n)):
        if n[i]==".":
            flag=0
        else:
            d.append(n[i])
            if flag==0:
                cnt=cnt-1
    for i in range(cnt):
        d.append("0")
    n=int("".join(d))
    #print(n)
    count2=0
    count5=0
    #print(n,kake)
    while n%2==0:
        n=n//2
        count2=count2+1
    while n%5==0:
        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,18-j)
        min5=max(0,18-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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from decimal import Decimal

N = int(input())
A = [int(10**9*Decimal(input())) for _ in range(N)]

def count(a,p):
  n = a
  count = 0
  while n%p == 0 and count<18:
    n //= p
    count += 1
  return count

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2 = count(a,2)
  c5 = count(a,5)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Submission status: Accepted

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

def pow25(x):
  f2=f5=0
  while x%2==0:
    x//=2
    f2+=1
  while x%5==0:
    x//=5
    f5+=1
  return f2,f5

pow25_dic=defaultdict(int)
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))    
    bunshi=10**9*seisu+shosu
  else:
    bunshi=10**9*int(a)
    
  pow25_dic[pow25(bunshi)]+=1
#print(pow25_dic)

pow25_key_list=[]
for key in pow25_dic:
  pow25_key_list.append(key)
#print(pow25_key_list)

answer=0
for i in range(len(pow25_key_list)):
  f2,f5=pow25_key_list[i]
  value=pow25_dic[(f2,f5)]
  if f2>=9 and f5>=9:    
    answer+=value*(value-1)//2
    
  for j in range(i+1,len(pow25_key_list)):
    f2_2,f5_2=pow25_key_list[j]
    if f2+f2_2>=18 and f5+f5_2>=18:
      value2=pow25_dic[(f2_2,f5_2)]
      answer+=value*value2
      
print(answer)