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:
import bisect
from decimal import Decimal
N, *A = open(0).read().split()
N = int(N)
c = [[0, 0] for _ in range(N)]
for i, a in enumerate(A):
    if '.' in a:
        p, q = a.split('.')
        q += '0' * (9 - len(q))
    else:
        p = a
        q = '0' * 9
    a = int(p + q)
    while True:
        if a % 2:
            break
        c[i][0] += 1
        a //= 2
    while True:
        if a % 5:
            break
        c[i][1] += 1
        a //= 5
c.sort()

#cum[i][j]:c[x][1]>=i (j<=x)となるようなxの個数
cum = [[0] * (N + 1) for _ in range(19)]
for i in range(19):
    for j in range(N - 1, -1, -1):
        cum[i][j] = cum[i][j + 1]
        if c[j][1] >= i:
            cum[i][j] += 1
ans = 0
for i, c2c5 in enumerate(c):
    c2, c5 = c2c5
    if c2 > 9 or (c2 == 9 and c5 >= 9):
        i2 = i + 1
    else:
        i2 = bisect.bisect_left(c, [18 - c2, -1])
    ans += cum[18 - c5][i2]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=[]
PRECISION_DIGITS=9
NO_ENTRY = 0
ARR_SIZE=PRECISION_DIGITS*2+1
cnt=np.full((ARR_SIZE,ARR_SIZE),NO_ENTRY,int)
# cnt=np.zeros((PRECISION_DIGITS*2,PRECISION_DIGITS*2),int)

# print(cnt)

for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*10**PRECISION_DIGITS)
	#print(tmpA)

	five = 0
	two = 0
	# (10**9) -> (two,five)=(9,9)
	# min = 10**-9, ignore < 10**9 ???
	while (tmpA % 2) == 0 and two < PRECISION_DIGITS*2:
		two += 1
		tmpA //= 2
	while (tmpA % 5) == 0 and five < PRECISION_DIGITS*2:
		five += 1
		tmpA //= 5

	if cnt[two][five] == NO_ENTRY:
		cnt[two][five]=1
	else:
		cnt[two][five]+=1

# print(cnt)
ans = 0

for x1 in range(ARR_SIZE):
	for y1 in range(ARR_SIZE):
		if cnt[x1][y1] == NO_ENTRY:
			continue

		for x2 in range(ARR_SIZE):
			for y2 in range(ARR_SIZE):
				if cnt[x2][y2] == NO_ENTRY:
					continue
				# 2**a(a>=0) and 5**b(b>=0) => integer
				if 0 <= x1+x2 - PRECISION_DIGITS*2 and 0 <= y1+y2 -PRECISION_DIGITS*2:
					if x1 == x2 and y1 == y2:
						# same entry
						# Total number of combinations choose 2 items
						# nC2 = n*(n-1)/2
						ans += int((cnt[x1][y1]*(cnt[x2][y2]-1))//2)
					else:
						ans += int(cnt[x1][y1]*cnt[x2][y2])

		# count up completed entry
		cnt[x1][y1] = NO_ENTRY

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
PRECISION_DIGITS=9
cnt={}


for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*10**PRECISION_DIGITS)
	#print(tmpA)

	five = 0
	two = 0
	while (tmpA % 2) == 0:
		two += 1
		tmpA //= 2
	while (tmpA % 5) == 0:
		five += 1
		tmpA //= 5

	# (10**9) -> (two,five)=(9,9)
	two -= PRECISION_DIGITS
	five -= PRECISION_DIGITS

	if (two,five) in cnt:
		cnt[(two,five)]+=1
	else:
		cnt[(two,five)]=1

# print(cnt)
ans = 0
for t1, cnt1 in cnt.items():
	for t2, cnt2 in cnt.items():
		# 2**a(a>=0) and 5**b(b>=0) => integer
		if 0 <= t1[0]+t2[0] and 0 <= t1[1]+t2[1]:
			if t1 < t2:
				ans += int(cnt1*cnt2)
			elif t1 == t2:
				# same entry
				# Total number of combinations choose 2 items
				# nC2 = n*(n-1)/2
				ans += int((cnt1*(cnt2-1))/2)


print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
PRECISION_DIGITS=9
cnt={}


for n in range(N):
	tmpA = float(input())
	tmpA = round(tmpA*(10**PRECISION_DIGITS))
	#print(tmpA)

	two = 0
	five = 0
	while (tmpA % 2) == 0:
		two += 1
		tmpA /= 2
	while (tmpA % 5) == 0:
		five += 1
		tmpA /= 5

	if (two,five) in cnt:
		cnt[(two,five)]+=1
	else:
		cnt[(two,five)]=1

keys=sorted(cnt.keys())
# print(keys)
ans = 0
for t1 in keys:
	for t2 in keys:
		# 2**a(a>=0) and 5**b(b>=0) => integer
		if 18 <= t1[0]+t2[0] and 18 <= t1[1]+t2[1]:
			cnt1 = cnt[(t1[0],t1[1])]
			cnt2 = cnt[(t2[0],t2[1])]
			if t1 < t2:
				ans += int(cnt1*cnt2)
			elif t1 == t2:
				# same entry
				# Total number of combinations choose 2 items
				# nC2 = n*(n-1)/2
				ans += int(cnt1*(cnt1-1)/2)


print(ans)

Submission status: Accepted

Solution code:
#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())

dp = [[0]*100 for _ in range(100)]

ans = 0

for i in range(n):
    s = readline().rstrip().decode('utf-8')
    res = int(Decimal(s)*(10**9))
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    #最悪10**13になるので、2**44,5**19の用意が必要
    for i in range(18-t,45):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)

Submission status: Accepted

Solution code:
#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())

dp = [[0]*100 for _ in range(100)]

ans = 0

for i in range(n):
    s = readline().rstrip().decode('utf-8')
    res = int(Decimal(s)*(10**9))
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,45):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)

Submission status: Accepted

Solution code:
#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1  = [] 
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    lst1.append(int(Decimal(s)*(10**9)))

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

ans = 0

for i in range(n):
    res = lst1[i]
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,45):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
X=[[0]*19 for _ in range(19)]
def f(num, x):
  ans=0
  while num%x==0:
    ans+=1
    num//=x
  return min(ans, 18)

A=[[0, 0] for _ in range(N)]

for i in range(N):
  tmp=input()
  if tmp[0]=='0':
    tmp=tmp[2:]
    tmp=int(tmp+'0'*(9-len(tmp)))
    A[i][0]=f(tmp, 2)
    A[i][1]=f(tmp, 5)
    X[A[i][0]][A[i][1]]+=1
  elif tmp.count('.')>0:
    ten=tmp.index('.')
    tmp=tmp.replace('.', '')
    tmp=int(tmp+'0'*(9-(len(tmp)-ten)))
    A[i][0]=f(tmp, 2)
    A[i][1]=f(tmp, 5)
    X[A[i][0]][A[i][1]]+=1
  else:
    tmp=int(tmp+'0'*9)
    A[i][0]=f(tmp, 2)
    A[i][1]=f(tmp, 5)
    X[A[i][0]][A[i][1]]+=1
    
for i in range(0, 19):
  for j in range(17, -1, -1):
    X[i][j]+=X[i][j+1]

ans=0
for i in range(N):
  for j in range(18-A[i][0], 19):
    ans+=X[j][18-A[i][1]]
  if A[i][0]>=9 and A[i][1]>=9:
    ans-=1
  
print(ans//2)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        #A1 ... AnのBIT(1-indexed)
        self.BIT = [0] * (n + 1)
        self.n = n

    #A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    #Ai += x O(logN)
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return
def get_int(f):
    if "." not in f:
        return int(f),0
    return int(f.replace(".","")),len(f)-f.index(".")-1
n = int(input())
p = [0] * n
for i in range(n):
    a, b = get_int(input())
    c, d = 0, 0
    while a % 2 == 0:
        c += 1
        a //= 2
    while a % 5 == 0:
        d += 1
        a //= 5
    c -= b
    d -= b
    p[i] = (c, d)
p.sort()

now = n - 1
t = BIT(50)
ans = 0
for i in range(n):
    for j in range(now, i, -1):
        if p[i][0] + p[j][0] >= 0:
            t.add(-p[j][1] + 25, 1)
            now -= 1
        else:
            break
    if now < i:
        t.add(-p[i][1] + 25, -1)
    ans += max(0, t.query(25 + p[i][1]))

print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        #A1 ... AnのBIT(1-indexed)
        self.BIT = [0] * (n + 1)
        self.n = n

    #A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    #Ai += x O(logN)
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return
def get_int(f):
    if "." not in f:
        return int(f),0
    return int(f.replace(".","")),len(f)-f.index(".")-1
n = int(input())
p = []
for i in range(n):
    a, b = get_int(input())
    c, d = 0, 0
    while a % 2 == 0:
        c += 1
        a //= 2
    while a % 5 == 0:
        d += 1
        a //= 5
    c -= b
    d -= b
    p.append((c, d))
p.sort(key=lambda x:x[0])
now = n - 1
t = BIT(50)
ans = 0
for i in range(n):
    for j in range(now, i, -1):
        if p[i][0] + p[j][0] >= 0:
            t.add(-p[j][1] + 25, 1)
            now -= 1
        else:
            break
    if now < i:
        t.add(-p[i][1] + 25, -1)
    ans += max(0, t.query(25 + p[i][1]))

print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        #A1 ... AnのBIT(1-indexed)
        self.BIT = [0] * (n + 1)
        self.n = n

    #A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    #Ai += x O(logN)
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return
def get_int(f):
    if "." not in f:
        return int(f),0
    return int(f.replace(".","")),len(f)-f.index(".")-1
n = int(input())
p = []
for i in range(n):
    a, b = get_int(input())
    c, d = 0, 0
    while a % 2 == 0:
        c += 1
        a //= 2
    while a % 5 == 0:
        d += 1
        a //= 5
    c -= b
    d -= b
    p.append((c, d))
p.sort()
now = n - 1
t = BIT(50)
ans = 0
for i in range(n):
    for j in range(now, i, -1):
        if p[i][0] + p[j][0] >= 0:
            t.add(-p[j][1] + 25, 1)
            now -= 1
        else:
            break
    if now < i:
        t.add(-p[i][1] + 25, -1)
    ans += max(0, t.query(25 + p[i][1]))

print(ans)

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
A = [input() for i in range(N)]

C = collections.defaultdict(int)
for i, x in enumerate(A):
    idx = 0
    x = x[:-1]
    if '.' in x:
        idx = x[::-1].index('.')
        x = x.replace('.', '')
    x = int(x)
    count2 = -idx
    count5 = -idx
    while(x % 2 == 0):
        x = x // 2
        count2 += 1

    while(x % 5 == 0):
        x = x // 5
        count5 += 1
    C[(count2, count5)] += 1
ans = 0
for a, b in C:
    for a2, b2 in C:
        if a+a2 >= 0 and b+b2 >= 0:
            if a == a2 and b == b2:
                ans += C[(a, b)]*(C[(a, b)]-1)
            else:
                ans += C[(a, b)]*C[(a2, b2)]
print(ans//2)

Submission status: Accepted

Solution code:

def s2int(a):
    dot_idx = -1
    for j in range(len(a)):
        if a[j] == '.':
            dot_idx = j
            break
    # .がないので末尾につける
    if dot_idx == -1:
        a += ".000000000"
    # .の場所に応じて後ろにつける
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmps = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmps += a[j]
    return int(tmps)

def Count_two_five(x):
    c2 = 0
    c5 = 0
    while x > 0 and x % 2 == 0:
        x //= 2
        c2 += 1
    while x > 0 and x % 5 == 0:
        x //= 5
        c5 += 1
    c2 = min(c2, 18)
    c5 = min(c5, 18)
    return c2, c5

def main():
    N = int(input())

    C2 = [0] * N
    C5 = [0] * N

    for i in range(N):
        C2[i], C5[i] = Count_two_five(s2int(str(input())))

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

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

    ans = 0
    for i in range(N):
        Cc[C2[i]][C5[i]] -= 1

        for j in range(19):
            for k in range(19):
                if C2[i] + j >= 18 and C5[i] + k >= 18:
                    ans += Cc[j][k]

        Cc[C2[i]][C5[i]] += 1

    print(ans//2)

main()

Submission status: Accepted

Solution code:

def s2int(a):
    dot_idx = -1
    for j in range(len(a)):
        if a[j] == '.':
            dot_idx = j
            break
    # .がないので末尾につける
    if dot_idx == -1:
        a += ".000000000"
    # .の場所に応じて後ろにつける
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmps = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmps += a[j]
    return int(tmps)

def Count_two_five(x):
    c2 = 0
    c5 = 0
    while x > 0 and x % 2 == 0:
        x //= 2
        c2 += 1
    while x > 0 and x % 5 == 0:
        x //= 5
        c5 += 1
    c2 = min(c2, 18)
    c5 = min(c5, 18)
    return c2, c5

def main():
    N = int(input())

    C2 = [0] * N
    C5 = [0] * N

    for i in range(N):
        C2[i], C5[i] = Count_two_five(s2int(str(input())))

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

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

    ans = 0
    for i in range(N):
        Cc[C2[i]][C5[i]] -= 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]
        Cc[C2[i]][C5[i]] += 1

    print(ans//2)

main()

Submission status: Accepted

Solution code:

def s2int(a):
    dot_idx = -1
    for j in range(len(a)):
        if a[j] == '.':
            dot_idx = j
            break
    # .がないので末尾につける
    if dot_idx == -1:
        a += ".000000000"
    # .の場所に応じて後ろにつける
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmps = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmps += a[j]
    return int(tmps)

def Count_two_five(x):
    c2 = 0
    c5 = 0
    while x > 0 and x % 2 == 0:
        x //= 2
        c2 += 1
    while x > 0 and x % 5 == 0:
        x //= 5
        c5 += 1
    c2 = min(c2, 18)
    c5 = min(c5, 18)
    return c2, c5

N = int(input())

C2 = [0] * N
C5 = [0] * N

for i in range(N):
    C2[i], C5[i] = Count_two_five(s2int(str(input())))

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

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

ans = 0
for i in range(N):
    Cc[C2[i]][C5[i]] -= 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]
    Cc[C2[i]][C5[i]] += 1

print(ans//2)

Submission status: Accepted

Solution code:
N = int(input())

C2 = [0] * N
C5 = [0] * N

for i in range(N):
    a = str(input())
    dot_idx = -1
    for j in range(len(a)):
        if a[j] == '.':
            dot_idx = j
            break
    # .がないので末尾につける
    if dot_idx == -1:
        a += ".000000000"
    # .の場所に応じて後ろにつける
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmps = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmps += a[j]
    
    b = int(tmps)

    # 素因数2の個数
    tmp = b
    while tmp > 0 and tmp % 2 == 0:
        tmp //= 2
        C2[i] += 1
    while tmp > 0 and tmp % 5 == 0:
        tmp //= 5
        C5[i] += 1
    C2[i] = min(C2[i], 18)
    C5[i] = min(C5[i], 18)

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

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

ans = 0
for i in range(N):
    Cc[C2[i]][C5[i]] -= 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]
    Cc[C2[i]][C5[i]] += 1

print(ans//2)

Submission status: Accepted

Solution code:
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
# precise but slow
# from math import floor
# from fractions import Fraction
# a, b = input().split()
# a = int(a)
# b = Fraction(b)
# print(floor(a * b))
# fast but only decimal fixed point
import sys,collections
from math import floor
from decimal import Decimal
N = int(sys.stdin.readline())
a = tuple(sys.stdin.readline().rstrip() for _ in range(N)) # multi line with single param
a = [int(Decimal(e)*1000000000) for e in a]

d = collections.defaultdict(int)
for e in a:#200 000
    b = e
    t = 0
    while b != 0 and b % 2 == 0:
        t += 1
        b = b//2
    b = e
    f = 0
    while b != 0 and b % 5 == 0:
        f += 1
        b = b//5
    d[(min(f,18),min(t,18))] += 1

ret = 0
for ft1,v1 in d.items():
    for ft2,v2 in d.items():
        f1,t1 = ft1
        f2,t2 = ft2
        if ft1 < ft2:
            continue
        if f1+f2 >= 18 and t1+t2 >= 18:
            if ft1 == ft2:
                ret += (v1*(v2-1))//2
            else:
                ret += v1*v2
print(ret)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  tmp=float(input())*10**9
  if tmp%1>0.9:
    tmp+=0.1
  A.append(int(tmp))

#print(A)

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

B=[]

for i in range(N):
  dev2,dev5=0,0
  while A[i]%2==0 and dev2<18:
    dev2+=1
    A[i]//=2
  while A[i]%5==0 and dev5<18:
    dev5+=1
    A[i]//=5
  dat[dev2][dev5]+=1
  B.append([dev2,dev5])
  
for i in range(19):
  for j in range(19):
    for k in range(i+1):
      for l in range(j+1):
        rui[k][l]+=dat[i][j]
  
ans=0
for i in range(N):
  dev2,dev5=B[i]
  t_dev2,t_dev5=18-dev2,18-dev5
  if dev2>=t_dev2 and dev5>=t_dev5:
    ans-=1
  ans+=rui[t_dev2][t_dev5]

print(ans//2)

Submission status: Accepted

Solution code:
N = int(input())

C2 = [0] * N
C5 = [0] * N

for i in range(N):
    a = str(input())
    dot_idx = -1
    for j in range(len(a)):
        if a[j] == '.':
            dot_idx = j
            break
    # .がないので末尾につける
    if dot_idx == -1:
        a += ".000000000"
    # .の場所に応じて後ろにつける
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmps = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmps += a[j]
    
    b = int(tmps)

    # 素因数2の個数
    tmp = b
    while tmp > 0 and tmp % 2 == 0:
        tmp //= 2
        C2[i] += 1
    while tmp > 0 and tmp % 5 == 0:
        tmp //= 5
        C5[i] += 1

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())
A = []
B = []
C2 = [0] * N
C5 = [0] * N


for i in range(N):
    a = str(input())
    ok = False
    dot_idx = -1
    l = len(a)
    for j in range(l):
        if a[j] == '.':
            ok = True
            dot_idx = j
    if dot_idx == -1:
        a += ".000000000"
    else:
        while len(a) < 10+dot_idx:
            a += "0"
    tmp = ""
    for j in range(len(a)):
        if a[j] == '.':continue
        tmp += a[j]

    B.append(int(tmp))
    tmp = B[i]
    tmp2 = B[i]
    while tmp > 0:
        if tmp % 2 == 0:
            tmp //= 2
            C2[i] += 1
        else:
            break
    while tmp2 > 0:
        if tmp % 5 == 0:
            tmp //= 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:
#mult 10**9 
import sys
input = sys.stdin.readline
from decimal import Decimal
from math import gcd
from collections import Counter
n=int(input())
a=[int(Decimal(input())*10**9) for _ in range(n)]

tf = []

for i in range(n):
    t=0;f=0;
    while a[i]%2==0:
        t+=1
        a[i]//=2
    while a[i]%5==0:
        f+=1
        a[i]//=5
    tf.append((t-9,f-9))

ctf = Counter(tf)
ans=0
for t,f in ctf:
    for t2,f2 in ctf:
        if t+t2>=0 and f+f2>=0:
            if t!=t2 or f!=f2:
                ans+= ctf[(t,f)]*ctf[(t2,f2)]
            else:
                ans+= ctf[(t,f)]*(ctf[(t,f)]-1)
print(ans//2)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  #tmp=float(input())*10**9
  inp=input()
  ten=inp.find(".")
  L=len(inp)
  batu=9
  if ten!=-1:
    batu-=L-ten-1
  inp=inp.replace(".","")
  inp=int(inp)
  inp*=10**batu
  A.append(inp)

#print(A)

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

B=[]

for i in range(N):
  dev2,dev5=0,0
  while A[i]%2==0 and dev2<18:
    dev2+=1
    A[i]//=2
  while A[i]%5==0 and dev5<18:
    dev5+=1
    A[i]//=5
  dat[dev2][dev5]+=1
  B.append([dev2,dev5])
  
for i in range(19):
  for j in range(19):
    for k in range(i+1):
      for l in range(j+1):
        rui[k][l]+=dat[i][j]
  
ans=0
for i in range(N):
  dev2,dev5=B[i]
  t_dev2,t_dev5=18-dev2,18-dev5
  if dev2>=t_dev2 and dev5>=t_dev5:
    ans-=1
  ans+=rui[t_dev2][t_dev5]

print(ans//2)

Submission status: Accepted

Solution code:
from numpy import*
def main():
  c=zeros((50,50),int_)
  r=0
  for a in[*open(0)][1:]:
    a=round(float(a)*1e9)
    y=0
    while a%5<1:
      a//=5
      y+=1
    x=int(log2(a&-a))
    r+=sum(c[max(0,18-x):,max(0,18-y):])
    c[x][y]+=1
  print(r)
main()

Submission status: Accepted

Solution code:
c=eval('[0]*50,'*50)
r=0
for a in[*open(0)][1:]:
 a=round(float(a)*1e9);y=1
 while a%5**y<1:y+=1
 x=len(bin(a&-a));r+=sum(sum(d[max(0,20-y):])for d in c[max(0,24-x):]);c[x][y]+=1
print(r)

Submission status: Accepted

Solution code:
c=eval('[0]*50,'*50)
r=0
for a in[*open(0)][1:]:
 a=round(float(a)*1e9);x=y=1
 while a%2**x<1:x+=1
 while a%5**y<1:y+=1
 r+=sum(sum(d[max(0,20-y):])for d in c[max(0,20-x):]);c[x][y]+=1
print(r)

Submission status: Accepted

Solution code:
def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
d = defaultdict()

for _ in range(n):
    a = input()
    if '.' in a:
        b = a.split('.')
        a = int(b[0] + b[1])
        cnt2 = -len(b[1])
        cnt5 = -len(b[1])
    else:
        a = int(a)
        cnt2 = 0
        cnt5 = 0
    while a % 2 == 0:
        cnt2 += 1
        a //= 2
    while a % 5 == 0:
        cnt5 += 1
        a //= 5
    if (cnt2, cnt5) in d:
        d[(cnt2, cnt5)] += 1
    else:
        d[(cnt2, cnt5)] = 1

ans = 0

for k1, v1 in d.items():
    for k2, v2 in d.items():
        x1, y1 = k1
        x2, y2 = k2
        if k1 != k2:
            if x1 + x2 >= 0 and y1 + y2 >= 0:
                ans += v1 * v2
        else:
            if x1 + x2 >= 0 and y1 + y2 >= 0:
                ans += v1 * (v1 - 1)

print(ans // 2)

Submission status: Accepted

Solution code:
c=eval('[0]*50,'*50)
r=0
for a in[*open(0)][1:]:
 a=round(float(a)*1e9);x=y=0
 while a%2<1:a//=2;x+=1
 while a%5<1:a//=5;y+=1
 r+=sum(sum(d[max(0,18-y):])for d in c[max(0,18-x):]);c[x][y]+=1
print(r)

Submission status: Accepted

Solution code:
import collections

def calc(n):
  cnt_2=0
  cnt_5=0
  while n%2==0 and cnt_2<18:
    cnt_2+=1
    n//=2
  while n%5==0 and cnt_5<18:
    cnt_5+=1
    n//=5
  return [cnt_2,cnt_5]

n=int(input())
dic=collections.defaultdict(int)
ans=0
for _ in range(n):
  tmp=input()
  if '.' in tmp:
    pos=tmp.index('.')
    d=len(tmp)-(pos+1)
    tmp=tmp[:pos]+tmp[pos+1:]+'0'*(9-d)
  else:
    tmp+='0'*9
  tmp=int(tmp)
  cnt_2,cnt_5=calc(tmp)
  dic[(cnt_2,cnt_5)]+=1
  if 18<=min(cnt_2*2,cnt_5*2):
    ans-=1
for a1,b1 in dic.keys():
  for a2,b2 in dic.keys():
    if min(a1+a2,b1+b2)>=18:
      ans+=dic[(a1,b1)]*dic[(a2,b2)]
print(ans//2)

Submission status: Accepted

Solution code:
c=eval('[0]*50,'*50)
r=0
for a in[*open(0)][1:]:
 a=round(float(a)*10**9);x=y=0
 while a%2<1:a//=2;x+=1
 while a%5<1:a//=5;y+=1
 r+=sum(sum(d[max(0,18-y):])for d in c[max(0,18-x):]);c[x][y]+=1
print(r)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    s25 = [[0]*19 for i in range(19)] #2^i*5^j*kの個数：s25[i][j]
    nms = [] #(i,j)の組
    n = int(ipt())
    for _ in range(n):
        a = float(ipt())*(10**9)+0.1
        ia = int(a)
        for i in range(19):
            if ia%2 != 0:
                t2 = i
                break
            elif i == 18:
                t2 = 18
            else:
                ia //= 2
        for i in range(19):
            if ia%5 != 0:
                t5 = i
                break
            elif i == 18:
                t5 = 18
            else:
                ia //= 5
        s25[18-t2][18-t5] += 1
        nms.append((t2,t5))

    ss = s25
    for i in range(1,19):
        ss[0][i] += ss[0][i-1]
        ss[i][0] += ss[i-1][0]
    for i in range(1,19):
        for j in range(1,19):
            ss[i][j] += ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]
#    print(ss)

    ans = 0
    for t2,t5 in nms:
        ans += ss[t2][t5]
        if t2 >= 9 and t5 >= 9:
            ans -= 1

    print(ans//2)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = int(float(input())*10**9+0.01)
    d2 = 0
    d5 = 0
    while True:
        if d % 2 != 0 and d % 5 != 0:
            break
        if d % 2 == 0:
            d //= 2
            d2 += 1
        if d % 5 == 0:
            d //= 5
            d5 += 1
    a.append((d2,d5))
    r[(d2,d5)] = r.get((d2,d5),0) + 1
ans = 0
for x , y in r.keys():
    for i , j in r.keys():
        if min(x+i,y+j) >= 18:
            ans += r[(x,y)]*r[(i,j)]
            if x == i and y == j:
                ans -= r[(x,y)]
                
print(ans//2)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
from collections import defaultdict
dic = defaultdict(int)
for _ in range(N):
    a = float(input())*(10**9)
    a = int(a+0.1)
    num2, num5 = 0, 0
    while a%2==0:
        a//=2
        num2+=1
        if num2>18: break
    while a%5==0:
        a//=5
        num5+=1
        if num5>18: break
    dic[(num2, num5)] += 1

keys = list(dic.keys())
length = len(keys)
ans = 0
for i in range(length):
    a2, a5 = keys[i]
    a_cnt = dic[(a2, a5)]
    for j in range(i, length):
        b2, b5 = keys[j]
        b_cnt = dic[(b2, b5)]
        if a2+b2>=18 and a5+b5>=18:
            if i==j:
                ans += (a_cnt)*(b_cnt-1)//2
            else:
                ans += a_cnt*b_cnt
print(ans)

Submission status: Accepted

Solution code:
from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = int(float(input())*10**9 + 0.1)
    d2 = 0
    d5 = 0
    while True:
        if d % 2 != 0 and d % 5 != 0:
            break
        if d % 2 == 0:
            d //= 2
            d2 += 1
        if d % 5 == 0:
            d //= 5
            d5 += 1
    a.append((d2,d5))
    r[(d2,d5)] = r.get((d2,d5),0) + 1
ans = 0
for x , y in r.keys():
    for i , j in r.keys():
        if min(x+i,y+j) >= 18:
            ans += r[(x,y)]*r[(i,j)]
            if x == i and y == j:
                ans -= r[(x,y)]
                
print(ans//2)

Submission status: Accepted

Solution code:
import collections

def calc(n):
  cnt_2=0
  cnt_5=0
  while n%2==0:
    cnt_2+=1
    n//=2
  while n%5==0:
    cnt_5+=1
    n//=5
  if cnt_2>18:
    cnt_2=18
  if cnt_5>18:
    cnt_5=18
  return [cnt_2,cnt_5]

n=int(input())
dic=collections.defaultdict(int)
ans=0
for _ in range(n):
  tmp=input()
  if '.' in tmp:
    pos=tmp.index('.')
    d=len(tmp)-(pos+1)
    tmp=tmp[:pos]+tmp[pos+1:]
  else:
    d=0
  tmp=int(tmp)
  cnt_2,cnt_5=calc(tmp)
  dic[(cnt_2,cnt_5,d)]+=1
  if 2*d<=min(cnt_2*2,cnt_5*2):
    ans-=1
for a1,b1,d1 in dic.keys():
  for a2,b2,d2 in dic.keys():
    if min(a1+a2,b1+b2)>=d1+d2:
      ans+=dic[(a1,b1,d1)]*dic[(a2,b2,d2)]
print(ans//2)