Problem:


Score : 300 points

Problem Statement

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

Constraints

2 \leq N \leq 200\,000

0 < A_i < 10^4

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

Input

Input is given from Standard Input in the following format.

N
A_1
A_2
\vdots
A_N

Output

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

Sample Input 1

5
7.5
2.4
17.000000001
17
16.000000000

Sample Output 1

3

There are 3 pairs with integer product:

7.5 \cdot 2.4 = 18

7.5 \cdot 16 = 120

17 \cdot 16 = 272

Sample Input 2

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

Sample Output 2

8



Sample input:
5
7.5
2.4
17.000000001
17
16.000000000


Sample output:
3

Submission status: Wrong Answer

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
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):
  s=int(float(input())*(10**9))
  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)

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    a = [float(input().rstrip()) for _ in range(n)]
    a_li = list(itertools.combinations(a, 2))
    ans = 0
    for i in a_li:
        f = i[0]*i[1]
        if f.is_integer():
            ans += 1
    print(ans)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import combinations
    N = int(input())
    As = [0.0]*N
    for i in range(N):
        As[i] = float(input())
    count = 0
    for i in range(N):
        for j in range(i+1, N):
            if As[i]*As[j] - int(As[i]*As[j]) == 0.0:
                count+=1




    return count

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
 
# 浮動小数点の入力
num_list = []
for i in range(a):
  num_list.append(float(input()))
 
count = 0
for i in num_list:
  for j in num_list:
    if i != j and isinstance(i*j, float):
      count += 1
 
# 出力
print("{}".format(int(count/2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(0, n):
    lst.append(float(input()) * 1e10)

sol = 0
for i in range(0, n - 1):
    for j in range(i + 1, n):
        mul = lst[i] * lst[j]
        if mul % 1e20 == 0:
            sol += 1

print(sol)

Submission status: Wrong Answer

Solution code:
n=int(input())
lst=[]
for i in range(n):
	lst.append(input())
c=0
for i in range(n-1):
	for j in range(i+1,n):
		product=float(lst[i])*float(lst[j])
		print(product)
		if product==int(product):
			c+=1
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input(""))
a = []
count = 0
 
for i in range(N):
  a.append(float(input("")))
  
for i in range(N-1):
    for j in range(i+1, N):
        if a[i]*a[j] - int(a[i]*a[j]) == 0:
            count += 1
          
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0 for x in range(N)]
count=0
for i in range(N):
    A[i] = float(input())
for i in range(N):
    for j in range(i+1,N):
        if int(A[i]*A[j])==float(A[i]*A[j]):
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
""" A
    https://atcoder.jp/contests/agc047/tasks/agc047_a
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return [lambda _: readIntegerSet(m) for _ in range(0, n)]

def main(N, A):
    count = 0
    for i in range(0, _N):
        for j in range(i+1, _N):
            C = A[i] * 1000000000 * A[j] * 1000000000
            if C % 1000000000000000000 == 0:
                count += 1

    return count

if __name__ == "__main__":
    _N = readInteger()
    _A = [float(readString()) for _ in range(0, _N)]

    print(main(_N, _A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(float(input()) * 10**9) for i in range(n)]
for i in range(n):
    if a[i]%(10**4) == 0:
        a[i] //= (10**4)
    else:
        a[i] = -1
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i] > 0 and a[j] > 0 and a[i]*a[j] %(10**10) == 0:
            ans += 1
            # print(a[i],a[j])
print(ans)
# print(a)

Submission status: Wrong Answer

Solution code:

n=int(input())
co=0
ss=[]
def gcd(aa,bb):
    if(aa==0):
        return bb
    else:
        return gcd(bb%aa,aa)

co=[0 for i in range(10001)]
ans=[]
pre=[[] for i in range(10001)]
for i in range(1,10001):
    for j in range(1,101):
        if(j*j>i):
            continue
        if(i%j==0):
            pre[i].append(j)
            if(j*j!=i):
                pre[i].append(i//j)
co2=0
for i in range(n):
    s=input()
    if('.' not in s):
        x=int(s)
        for j in pre[x]:
            co[j]+=1
        co2+=1
    else:
        x,y=s.split(".")
        nu=int(x)
        nu*=(10**len(y))
        nu+=int(y)
        de=10**len(y)
        gg=gcd(nu,de)
        nu//=gg
        de//=gg
        ans.append([nu,de])
fin=0
if(co2>1):
    fin+=(co2*(co2-1))//2
for i in ans:
   # print(i[0],i[1])
    if(i[1]>len(co)):
        continue
    fin+=co[i[1]]
print(fin)

Submission status: Wrong Answer

Solution code:
# problem a
# score 300
from collections import defaultdict
N = int(input())
A = []
for i in range(N):
    x = float(input())
    x = int(x*(10**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)

Submission status: Wrong Answer

Solution code:
n = int(input())
alis = []
ans = 0
for _ in range(0,n):
  a = float(input())
  alis.append(a)
  
for i in range(0,n):
  for j in range(0,i):
    if int(alis[i] * alis[j]) - alis[i] * alis[j] == 0:
      ans += 1
      
print(ans)

Submission status: Wrong Answer

Solution code:
###############################################
#                                             #
#   author: raghav_0901 (Raghav Dalmia)       #
#   updated on: 09-08-2020,  5:41:22 pm IST   #
#                                             #
###############################################


from math import *


def _in():
    arr = [int(x) for x in input().split(' ')]
    return arr[0] if len(arr) == 1 else arr


def isInt(n):
    n = n / (10**18)
    return floor(n) == ceil(n)


if __name__ == "__main__":
    n = int(input())
    arr = []
    for i in range(n):
        arr.append(float(input()))

    ans = 0
    for i in range(0, n - 1):
        for j in range(i + 1, n):
            if(isInt((arr[i] * (10**9)) * (arr[j] * (10**9)))):
                # print(arr[i], arr[j])
                ans = ans + 1

    print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
an = [float(input()) for i in range(N)]

length = len(an)

count = 0
for i in range(length):
    ai = an[i]
    for j in range(i + 1, length):
        aj = an[j]
        seki = ai * aj
        if seki == math.floor(seki):
            count = count + 1

print(count)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x = [float(input())]
ct = 0
for _ in range(n-1):
    no = float(input())
    for i in x:
        if (no*i)%1 == 0.0:
            #print("*",no,i,no*i)
            ct += 1
    x.append(no)
print(ct)

Submission status: Wrong Answer

Solution code:
N=int(input())
nums=[]
count=0
for i in range(N):
  a=float(input())
  nums.append(a)
k=1
for i in range(N):
  for j in range(k, N):
    if nums[i]*nums[j]==int(nums[i]*nums[j]):
      count+=1
    k+=1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [float(input()) for _ in range(N)]
cnt = 0
for i in range(len(S)):
    for j in range(i+1, len(S)):
        if (S[i]*S[j]).is_integer():
            cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

count = int(sys.stdin.readline())
values = []
for i in range(count):
    values.append(float(sys.stdin.readline()))
result = 0
for i in range(count):
    for j in range(i+1, count):
        value = values[i] * values[j]
        if int(value) == value:
            result += 1
print(result)

Submission status: Wrong Answer

Solution code:
data = []
count = 0
for i in input().split():
    data.append(i)

for i in range(len(data)):
    if i!=0:
        for j in range(len(data)):
            if(i<j):
                if(isinstance(data[i]*data[j],int)):
                    count +=1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
aarys = [float(input()) for _ in range(n)]
count = 0
for i in range(len(aarys)-1):
    for j in range(i+1, len(aarys)):
        if aarys[i] * aarys[j]%1 == 0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [float(input()) for _ in range(n)]
ans = 0

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = float(input())
from itertools import combinations
base = list(combinations(A,2))
ans=0
for i in range(len(base)):
    a=base[i][0]*base[i][1]
    if a.is_integer()==True:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [float(input()) for _ in range(n)]
ans = 0
# f = []
for i in range(n):
    for j in range(n):
        if i < j:
            p = sorted([arr[i],arr[j]])
            t = arr[i]*arr[j]
            # if int(t) == t and p not in f:
            if int(t) == t:
                ans += 1
            # f.append(p)
print(ans)
# print(f)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(0, n):
    lst.append(float(input()) * 1e9)

sol = 0
for i in range(0, n - 1):
    for j in range(i + 1, n):
        mul = lst[i] * lst[j]
        if mul % 1e18 == 0:
            sol += 1

print(sol)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = [input().split() for l in range(n)]
def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
t=0
for i in range(0,n-1):
    for j in range (i+1,n):
        if is_integer(i*j) == True:
            t=t+1
print(t)

Submission status: Wrong Answer

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

cnt = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        product = A[i] * A[j]
        print(f"{A[i]} * {A[j]} = {product}")
        print(f"mod = {product % 1.0}")
        if product % 1.0 == 0 and (product / A[j] == A[i]):
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = []
count = 0
for _ in range(n):
  arr.append(float(input()))
for i in range(n):
  for j in range(i+1,n):
    if arr[i] * arr[j] == int(arr[i]*arr[j]):
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
nums = []
for n in range(N):    nums.append(float(input()))
count = 0
for i in range(N):
    for j in range(i+1, N):
        if (nums[i]*nums[j]).is_integer():  count+=1
print(count)

Submission status: Wrong Answer

Solution code:
data = []
count = 0
for i in input().split():
    data.append(i)

for i in range(len(data)):
    if i!=0:
        for j in range(len(data)):
            if(i<j and j!=0):
                if(isinstance(data[i]*data[j],int)):
                    count +=1

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
l = [float(input()) for _ in range(n)]

c = 0
for i, j in itertools.combinations(l, 2):
  if (i * j).is_integer():
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
pairs = 0

for _ in range(n):
    a.append(float(input()))

for i, a_i in enumerate(a):
    for j, a_j in enumerate(a[i+1:]):
        if a_i * a_j == int(a_i * a_j):
            pairs += 1
print(pairs)

Submission status: Wrong Answer

Solution code:
arr = list()
for i in range(int(input())):
  arr.append(float(input()))
count = 0
for i in range(len(arr)):
  for j in range(i + 1, len(arr)):
    if int(arr[i] * arr[j]) - (arr[i] * arr[j]) >= 0:
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:

#import collections  
#from collections import defaultdict  
#for _ in range(int(input())):
import math
n=int(input())
#w=[int(x) for x in input().split()]
a=[]
for i in range(n):    
    a.append(float(input()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        x= a[i]*a[j]
        if x==math.ceil(x):
           ans+=1 
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [float(input()) * 10**9 for i in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]*a[j] %10**18 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
K = []
T = []
F = []
for _ in range(n):
  s = input()
  if "." not in s:
    s += "."
  a, b = s.split(".")
  k = len(b)
  c = int(a+b)
  t = 0
  while c%2 == 0:
    c //= 2
    t += 1
  T.append(t-k)
  f = 0
  while c%5 == 0:
    c //= 5
    f += 1
  F.append(f-k)
ans = 0
for i in range(n-1):
  t1, f1 = T[i], F[i]
  for j in range(i+1, n):
    t2, f2 = T[j], F[j]
    if 0 <= min(t1+t2, f1+f2):
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import decimal
n = int(input())
a=[input() for i in range(n)]
biga=[]
for i in range(n):
    num = decimal.Decimal(a[i])
    biga.append(int(num*10**9))
def fact25(n):
    cnt2=0
    cnt5=0
    while n%2==0:
        n//=2
        cnt2+=1
    while n%5==0:
        n//=5
        cnt5+=1
    return cnt2,cnt5

arr = [[0 for _ in range(20)] for _ in range(20)]
p25 = []
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    p25.append([cnt2,cnt5])
    cnt2=min(19,cnt2)
    cnt5=min(19,cnt5)
    arr[cnt2][cnt5]+=1
ans=0
for i in range(n):
    cnt2,cnt5=p25[i]
    n2=18-cnt2
    n5=18-cnt5
    cnt2=min(19,cnt2)
    cnt5=min(19,cnt5)
    arr[cnt2][cnt5]-=1
    for j in range(20): # 2
        for k in range(20): # 5
            if j>=n2 and k>=n5:
                ans+=arr[j][k]
    arr[cnt2][cnt5]+=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import decimal
n = int(input())
a=[input() for i in range(n)]
biga=[]
for i in range(n):
    num = decimal.Decimal(a[i])
    biga.append(int(num*10**9))
def fact25(n):
    cnt2=0
    cnt5=0
    while True:
        if n%2==0:
            n//=2
            cnt2+=1
        else:
            break
    while True:
        if n%5==0:
            n//=5
            cnt5+=1
        else:
            break
    return cnt2,cnt5
arr = [[0 for _ in range(50)] for _ in range(50)]
p25 = []
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    p25.append([cnt2,cnt5])
    arr[cnt2][cnt5]+=1
ans=0
for i in range(n):
    cnt2,cnt5=p25[i]
    n2=18-cnt2
    n5=18-cnt5
    arr[cnt2][cnt5]-=1
    for j in range(40): # 2
        for k in range(40): # 5
            if j>=n2 and k>=n5:
                ans+=arr[j][k]
    arr[cnt2][cnt5]+=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import decimal
n = int(input())
a=[input() for i in range(n)]
biga=[]
for i in range(n):
    num = decimal.Decimal(a[i])
    biga.append(int(num*10**9))

def fact25(n):
    cnt2=0
    cnt5=0
    while True:
        if n%2==0:
            n//=2
            cnt2+=1
        else:
            break
    while True:
        if n%5==0:
            n//=5
            cnt5+=1
        else:
            break
    return cnt2,cnt5

arr = [[0 for _ in range(50)] for _ in range(50)]
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    arr[cnt2][cnt5]+=1
ans=0
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    n2=18-cnt2
    n5=18-cnt5
    arr[cnt2][cnt5]-=1
    for j in range(50): # 2
        for k in range(50): # 5
            if j>=n2 and k>=n5:
                ans+=arr[j][k]
    arr[cnt2][cnt5]+=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
def prog(x):
    n = len(x)
    y = [int(i * 10**9) for i in x]
    #y

    def count25(n):
        two = five = 0
        while n % 2 == 0:
            two += 1
            n //= 2
        while n % 5 == 0:
            five += 1
            n //= 5
        return two, five

    two = [0] * n
    five = [0] * n
    for i in range(n):
        two[i], five[i] = count25(y[i])
    count = 0
    for i in range(n - 1):
        two_i = 18 - two[i]
        five_i = 18 - five[i]
        for j in range(i + 1, n):
            #if min(two[i] + two[j], five[i] + five[j]) >= 18:
            if two[j] >= two_i and five[j] >= five_i:
                #print(min(two1,two2) + min(five1, five2), two1, two2, five1, five2)
                #print(y[i] * y[j], (y[i] * y[j]) / 10**18)
                #print(y[i] / 10**9, y[j] / 10**9)
                #print('=================')
                count += 1
    print(count)

n = int(input())
x = [0] * n
x = [float(input()) for i in range(n)]
prog(x)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mat=[[0]*30 for _ in range(30)]
ary=[]
op=0
a=[]
for _ in range(n):
  t=list(input().split('.'))
  if len(t)==1:
    c=int(t[0])*pow(10,9)
  else:
    c=int(t[0])*pow(10,9)
    r=int((t[1]+'0'*10)[:9])
    c+=r
  n2,n5=0,0
  while (c//pow(2,n2))%2==0:
    n2+=1
  while (c//pow(5,n5))%5==0:
    n5+=1
  n2=min(n2,9+9)
  n5=min(n5,9+9)
  mat[n2][n5]+=1
  a.append((c,n2,n5))
  ary.append((n2,n5))
#for x in a:
#  print(x)
summat=[[0]*31 for _ in range(31)]
for i in range(30):
  for j in range(30):
    summat[i+1][j+1]=summat[i+1][j]+mat[i][j]
for i in range(30):
  for j in range(30):
    summat[i+1][j+1]+=summat[i][j+1]

ans=0
for n2,n5 in ary:
  t2,t5=n2,n5
  t2-=9
  t2*=-1
  t2+=9
  t5-=9
  t5*=-1
  t5+=9
  #print(n2,n5,t2,t5)
  ans+=summat[-1][-1]-summat[t2][-1]-summat[-1][t5]+summat[t2][t5]
  if n2>=9+op and n5>=9+op:ans-=1
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import decimal

N = int(input())
A = [int(decimal.Decimal(input()) * 10 ** 9) for _ in range(N)]
B = []
for a in A:
    cnt = 0
    while a % 10 == 0:
        cnt += 1
        a //= 10
    B.append((a, cnt))
ans = 0
for i in range(N):
    for j in range(i+1, N):
        x, cnt1 = B[i]
        y, cnt2 = B[j]
        if cnt1 + cnt2 >= 18:
            ans += 1
            continue
        z = x * y
        cnt3 = 0
        while z % 10 == 0:
            cnt3 += 1
            z //= 10
        if cnt1 + cnt2 + cnt3 >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f == 5:
                five += 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n == 2:
            two += 1
        if n == 5:
            five += 1
    return two, five


def main():
    n = ni()
    a = [int(decimal.Decimal(sys.stdin.readline()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    twoflg = False
    fiveflg = False
    for ai in a:
        two, five = prime_factorize(ai)

        if two >= 9:
            twoflg = True
        if five >= 9:
            fiveflg = True

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    if twoflg and fiveflg:
        for k, v in res.items():
            two, five = k
            for tk, tv in res.items():
                t_two, t_five = tk
                if two + t_two >= border and five + t_five >= border:
                    if two == t_two and five == t_five:
                        ans += v * (tv - 1)
                    else:
                        ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f == 5:
                five += 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n == 2:
            two += 1
        if n == 5:
            five += 1
    return two, five


def main():
    n = ni()
    a = [int(decimal.Decimal(input()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    twoflg = False
    fiveflg = False
    for ai in a:
        two, five = prime_factorize(ai)

        if two >= 9:
            twoflg = True
        if five >= 9:
            fiveflg = True

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    if twoflg and fiveflg:
        for k, v in res.items():
            two, five = k
            for tk, tv in res.items():
                t_two, t_five = tk
                if two + t_two >= border and five + t_five >= border:
                    if two == t_two and five == t_five:
                        ans += v * (tv - 1)
                    else:
                        ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f == 5:
                five += 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n == 2:
            two += 1
        if n == 5:
            five += 1
    return two, five


def main():
    n = ni()
    a = [int(decimal.Decimal(input()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    for ai in a:
        two, five = prime_factorize(ai)

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    for k, v in res.items():
        two, five = k
        for tk, tv in res.items():
            t_two, t_five = tk
            if two + t_two >= border and five + t_five >= border:
                if two == t_two and five == t_five:
                    ans += v * (tv - 1)
                else:
                    ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    n = ni()
    a = [int(decimal.Decimal(input()) * (10 ** 9)) for _ in range(n)]
    res = {}
    border = 18

    for ai in a:
        tmp = prime_factorize(ai)
        c = collections.Counter(tmp)
        two = 0
        five = 0
        if 2 in c.keys():
            two = c[2]
        if 5 in c.keys():
            five = c[5]

        if (two, five) not in res.keys():
            res[(two, five)] = 1
        else:
            res[(two, five)] += 1

    ans = 0
    for k, v in res.items():
        two, five = k
        for tk, tv in res.items():
            t_two, t_five = tk
            if two + t_two >= border and five + t_five >= border:
                if two == t_two and five == t_five:
                    ans += v * (tv - 1)
                else:
                    ans += v * tv

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Binary Index Tree (2-dimension)
class BIT2:
    # H*W, 0-based
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    #O(logH*logW)
    #[0.i)x[0.j)
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    # O(logH*logW)
    def add(self, i, j, x):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + x
                k|=(k+1)
            i|=(i+1)
    # [x0, x1) x [y0, y1)
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
ans=0
bit=BIT2(20,20)
for i in range(int(input())):
    a=input().split('.')
    if len(a)==1:
        cnt2,cnt5=9,9
        a=int(a[0])
        while a%2==0 and cnt2<18:
            cnt2+=1
            a//=2
        while a%5==0 and cnt5<18:
            cnt5+=1
            a//=5
    else:
        a=int(a[0])*10**9+int((a[1][::-1].zfill(9))[::-1])
        cnt2,cnt5=0,0
        for j in range(18):
            if a%2==0:
                a//=2
                cnt2+=1
            if a%5==0:
                a//=5
                cnt5+=1
    ans+=bit.range_sum(18-cnt2,19,18-cnt5,19)
    bit.add(cnt2,cnt5,1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

def main():
    N = int(input())
    A = [Decimal(input()) for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            tmp = '{:.20f}'.format(A[i] * A[j])
            if not '.' in tmp:
                cnt += 1
            else:
                a = tmp.split('.')[1]
                if len(a) == a.count('0'):
                    cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    ans = 0
    cnt = [[0]*20 for _ in range(45)]
    for _ in range(n):
        a = list(map(str, input().rstrip().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_2, cnt_5 = 0, 0
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(45):
            for j in range(20):
                if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                    ans += cnt[i][j]
        cnt[cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    ans = 0
    cnt = [[0]*45 for _ in range(45)]
    for _ in range(n):
        a = list(map(str, input().rstrip().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_2, cnt_5 = 0, 0
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(45):
            for j in range(45):
                if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                    ans += cnt[i][j]
        cnt[cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    ans = 0
    cnt = [[0]*60 for _ in range(60)]
    for _ in range(n):
        a = list(map(str, input().rstrip().split(".")))
        x = 0
        if len(a) == 1:
            x = int(a[0]) * 10**9
        else:
            x = int(a[0]) * 10**9 + int(a[1]) * pow(10, 9-len(a[1]))
        cnt_2, cnt_5 = 0, 0
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(60):
            for j in range(60):
                if cnt_2 + i >= 18 and cnt_5 + j >= 18:
                    ans += cnt[i][j]
        cnt[cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()