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: Time Limit Exceeded

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

def main():
    n = int(input())
    ans = 0
    cnt = [[[0]*80 for j in range(80)] for i in range(20)]
    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_10, cnt_2, cnt_5 = 0, 0, 0
        while x % 10 == 0:
            cnt_10 += 1
            x //= 10
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(15):
            if i + cnt_10 >= 18:
                for j in range(50):
                    ans += sum(cnt[i][j])
            else:
                p = 18 - cnt_10 - i
                if cnt_2 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][0][j]
                if cnt_5 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][j][0]
        cnt[cnt_10][cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    ans = 0
    cnt = [[[0]*80 for j in range(80)] for i in range(20)]
    for _ in range(n):
        a = list(map(str, input().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_10, cnt_2, cnt_5 = 0, 0, 0
        while x % 10 == 0:
            cnt_10 += 1
            x //= 10
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(15):
            if i + cnt_10 >= 18:
                for j in range(50):
                    ans += sum(cnt[i][j])
            else:
                p = 18 - cnt_10 - i
                if cnt_2 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][0][j]
                if cnt_5 >= p:
                    for j in range(p, 50):
                        ans += cnt[i][j][0]
        cnt[cnt_10][cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    ans = 0
    cnt = [[[0]*80 for j in range(80)] for i in range(20)]
    for _ in range(n):
        a = list(map(str, input().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_10, cnt_2, cnt_5 = 0, 0, 0
        while x % 10 == 0:
            cnt_10 += 1
            x //= 10
        while x % 2 == 0:
            cnt_2 += 1
            x //= 2
        while x % 5 == 0:
            cnt_5 += 1
            x //= 5
        for i in range(20):
            if i + cnt_10 >= 18:
                for j in range(80):
                    ans += sum(cnt[i][j])
            else:
                p = 18 - cnt_10 - i
                if cnt_2 >= p:
                    for j in range(p, 80):
                        ans += cnt[i][0][j]
                if cnt_5 >= p:
                    for j in range(p, 80):
                        ans += cnt[i][j][0]
        cnt[cnt_10][cnt_2][cnt_5] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#QN = map(int,input().split()) # 500
from decimal import Decimal

def isInt(i,j):
  res =  i * j
  return ((res % 1) == 0)

N = int(input())

vals = []
cnt = 0
for i in range(N):
  v = Decimal(input())
  for i in vals:
    if (isInt(i,v)):
      cnt +=1
  vals.append(v)

print("{}".format(cnt))

Submission status: Time Limit Exceeded

Solution code:
import copy

N = int(input())
A = []
for _ in range(N):
    A.append(float(input()))
B = copy.copy(A)
count = 0

for _i, i in enumerate(A):
    for _j, j in enumerate(B):
        if (i != j and float(i * j).is_integer()):
            count = count + 1
    B.remove(i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
x=int(input())
lst=[]
for a in range(x):
    n=float(input())
    lst.append(n)
b=0
c=1
ans=0
for d in lst:
    for e in lst:
        if(d!=e):
            if(str(d*e).endswith('.0')==True):
                ans+=1
print(int(ans/2))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = []
dic = DD(int)
for _ in range(N):
  s = S().split(".")
  if len(s) == 1:
    temp = int(s[0])*(10**9)
  else:
    temp = int(s[0])*(10**9)+int(s[1])*(10**(9-len(s[1])))
  _2,_5 = 0,0
  for p,n in factorization(temp):
    if p==2:_2 = min(n,18)
    if p==5:_5 = min(n,18)
  dic[(_2,_5)] += 1

ans1 = 0
ans2 = 0
for i2 in range(19):
  for j2 in range(18-i2,19):
    for i5 in range(19):
      for j5 in range(18-i5,19):
        if (i2,i5)==(j2,j5):
          ans1 += dic[(i2,i5)]*(dic[(j2,j5)]-1)
        else:
          ans2 += dic[(i2,i5)]*dic[(j2,j5)]

print((ans1+ans2)//2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = []

for _ in range(N):
  s = S().split(".")
  if len(s) == 1:
    A.append(int(s[0])*(10**9))
  else:
    A.append(int(s[0])*(10**9)+int(s[1])*(10**(9-len(s[1]))))
ans = 0
for i in range(N):
  for j in range(i+1,N):
    if not A[i]*A[j] % 10**18:
      ans += 1
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
N = int(input())
#numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  #numlist[i] = Decimal(input()) * 1000000000
  wk = Decimal(input()) * 1000000000

  #wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  numlist[i] = Decimal(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(i,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          if acc[i][j] > 0 and acc[k][l] > 0:
            Ans += acc[i][j] * acc[k][l]
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)

print(int(Ans))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
acc = [[0 for i in range(19)] for j in range(19)]
Ans = 0

for i in range(1,N+1):
  numlist[i] = Decimal(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break

  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break

  acc[log2[i]][log5[i]] += 1
    
for i in range(0,19):
  for j in range(0,19): 
    for k in range(0,19):
      for l in range(0,19):
        if (i + k) >= 18 and (j + l) >= 18 and (i < k or (i == k and j <= l)):
          #if acc[i][j] > 0 and acc[k][l] > 0:
          if True:
            Ans += acc[i][j] * acc[k][l]
            #if i >= 17 and j >= 9:
              #print("+["+str(i)+","+str(j)+"]["+str(k)+","+str(l)+"]")
              #print(str(acc[i][j])+"*"+str(acc[k][l]))
            #print("+:" + str(acc[i][j] * acc[k][l]))
            if i >= 9 and j >= 9 and i == k and j == l:
              Ans -= int((acc[i][j] * (acc[i][j] + 1)) / 2)
              #print("-["+str(i)+","+str(j)+"]["+str(k)+","+str(l)+"]")
              #print("-:" + str(acc[i][j]))


print(int(Ans))
#print(acc)

#s = sum(sum(acc,[]))
#print(s)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *

n = int(input())
arr = []
for _ in range(n):
    arr.append(Decimal(input()))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        a = arr[i]*arr[j]
        if a == a.quantize(Decimal('1.')):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [] 
for _ in range(n):
    arr.append( int(float(input())*1000000000) )

ans=0
for i in range(n):
    for j in range(i+1,n):
        if arr[i]*arr[j]%1000000000000000000==0:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[float(input()) for _ in range(n)]
cnt=[]*n
for i in a:
  x=int(i*1000000000)
  i2,i5=0,0
  while x%2==0:
    x//=2
    i2+=1
  while x%5==0:
    x//=5
    i5+=1
  cnt.append((i2,i5))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    x2,x5=cnt[i]
    y2,y5=cnt[j]
    if min(x2+y2,x5+y5)>=18:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

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

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n = ni()
    g = [BIT(20) for _ in range(19)]
    ans = 0
    for _ in range(n):
        a = input().split('.')
        x = int(a[0])*10**9
        if len(a) > 1:
            x += int(a[1] + '0' * (9-len(a[1])))
        t = 0; f = 0
        while x % 2 == 0:
            t += 1
            x //= 2
        while x % 5 == 0:
            f += 1
            x //= 5
        if t > 18: t = 18
        if f > 18: f = 18
        for i in range(18-f, 19):
            ans += g[i].bitsum(18-t, 19)
        g[f].bitadd(t, 1)
    print(ans)
    return

solve()

Submission status: Time Limit Exceeded

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

D = [[0 for j in range(40)] for i in range(60)]

for a in A:
    #まずは分子の整数Bと分母の指数kに分けていく
    B=0;k=0
    for j in range(len(a)):
        if a[j]!='.':
            B=B*10
            B=B+int(a[j])
        if a[j]=='.':
            k=len(a)-j-1
    
    #次にBに2と5がいくつ含まれるかを求める
    t=0;f=0
    b=B
    while b%2==0:
        t+=1
        b=b//2
    b=B
    while b%5==0:
        f+=1
        b=b//5
    
    #D[t-k][f-k]をインクリメントする
    #…と言いたいところだがマイナスになりうるので+10したものを入れる
    
    D[t-k+10][f-k+10]+=1
    

Ans=0
for i in range(len(D)):
    for j in range(len(D[i])):
        for k in range(len(D)):
            for l in range(len(D[k])):
                #(hoge*2^i*5^j)*(fuga*2^k*5^l)がOKならAnsに足し入れる
                if i+k-20>=0 and j+l-20>=0 and not(i==k and j==l):
                    Ans = Ans+D[i][j]*D[k][l]

#D[i][j]*D[k][l]とD[i][l]*D[i][j]で同じものを２回かけているので2で割っておく
Ans = Ans//2

#違うA_iでも同じt-k,f-kを持つことはある
#ので、それを処理する
for i in range(len(D)):
    for j in range(len(D[i])):
        if i-10>=0 and j-10>=0:
            Ans = Ans + D[i][j]*(D[i][j]-1)//2

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for i in range(N):
  x = a[i]
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc
print(res // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
res = 0
for i in range(N):
  x = a[i]
  cc = N
  for k in ks:
    z = x * k
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    if c >= 18:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc
print(res // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
d = dd(list)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz].append(i)
  a.append(zz)
#print(d)
res = 0
for i in range(N):
  x = a[i]
  for k in d.keys():
    z = x * k
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    if c < 18: continue
    res += bl(d[k], i)
    #print(x, k, bl(d[k], i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

n = int(input())
lst = []
for _ in range(n):
  lst.append(Decimal(input()))
count = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    k = lst[i] * lst[j]
    if k // 1 == k:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
import sys
input=sys.stdin.readline

def factorization(n):
    arr={}
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr[i]=cnt
    if(tmp!=1):
        arr[tmp]=1
    return arr

N=int(input())
A=[int(Decimal(input())*Decimal(1000000000)) for i in range(N)]
dic=[None for i in range(N)]
dp=[[0]*51 for i in range(51)]

for i in range(N):
    d=factorization(A[i])
    dp[d.get(2,0)][d.get(5,0)]+=1
    dic[i]=d

for i in reversed(range(51)):
    for j in reversed(range(51)):
        if i==50 and j==50:
            continue
        if i==50:
            dp[i][j]+=dp[i][j+1]
        elif j==50:
            dp[i][j]+=dp[i+1][j]
        else:
            dp[i][j]+=dp[i][j+1]+dp[i+1][j]-dp[i+1][j+1]
ans=0

for i in range(N):
    d=dic[i]
    a,b=d.get(2,0),d.get(5,0)
    t,f=max(18-a,0),max(18-b,0)
    res=dp[t][f]
    if t<=a and f<=b:
        res-=1
    ans+=res
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def decomp(m):
    pf=defaultdict(int)
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]+=1
            m//=i
    if m>1:pf[m]=1
    return (pf[2], pf[5])

n=int(input())
table=[[0]*50 for _ in range(50)]
ans=0
for i in range(n):
    a=input()
    ax=round(float(a)*(10**9))
    p2,p5=decomp(ax)
    if i!=0:
        for j in range(18-p2,19):
            ans+=sum(table[j][18-p5:])
    table[p2][p5]+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import decimal
n = int(input())
num = n
#num回のfloat型の入力を受け付け、listにする
list = [decimal.Decimal(input()) for i in range(num)]

# print(list)
count = 0

#list [0]-[n-1]
for i in range(n):
    for j in range(i+1, n):
        # print(str(i) + "  " + str(j) + "  " + str(list[i]) + "  " + str(list[j]) + "  " + str(list[i] * list[j] % 1))
        if list[i] * list[j] % 1 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
counter = 0
N = int(input())
lis = [0] * N
for i in range(0, N):
  s = input()
  if s.isdigit() == False:
    lis[i] = Decimal(s)
  else:
    lis[i] = int(s)
for i in range(0, N):
  for j in range(i+1, N):
    k = lis[i] * lis[j]
    b = k - int(k)
    if b == 0 or b == 0.0 or b == 0.00 or b == 0.000 or b == 0.0000 or b == 0.00000 or b == 0.000000 or b == 0.0000000 or b == 0.00000000:
      counter+= 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = count5 = 9
  while n%2==0 and count2<18:
    n //= 2
    count2 += 1
  while n%5==0 and count5<18:
    n //= 5
    count5 += 1
  return count2, count5

Z = [[0 for _ in range(19)] for _ in range(19)]
answer = 0
for a in A:
  c2, c5 = count(a)
  answer += Z[18-c2][18-c5]
  for i in range(c2+1):
    for j in range(c5+1):
      Z[i][j] += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
n = int(input())

a = []
for i in range(n):
    a.append(Decimal(input()))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if (a[i] * a[j]) % 1 == 0:
            ans += 1
            #print(a[i], a[j], a[i] * a[j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline

N = int(input())
An = [decimal.Decimal(input()) for _ in range(N)]
ans = 0
for i in range(N):
    if i * (10**9) % (10**9) != 0 and 5:
        continue
    for j in range(i+1, N):
        val = An[i] * An[j]
#        valf = float(val)
        if val == round(val):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline

N = int(input())
An = [decimal.Decimal(input()) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1, N):
        val = An[i] * An[j]
#        valf = float(val)
        if val == round(val):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

N = int(input())

A = []
for _ in range(N):
  A.append(Decimal(input()))

cnt = 0
for i in range(N):
  for j in range(i+1,N):
    if A[i]*A[j] == int(A[i]*A[j]):
      cnt += 1
      
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = []
for i in range(n):
    x = float(input())
    a.append(int(x*1000000000))
res = 0
for i in range(n):
    for j in range(i+1,n):
        x = a[i]*a[j]
        if x%1000000000000000000 == 0:
            res = res+1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def enum_divisors(n):
        # 約数列挙

        divisors = []

        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)

        return divisors

    import fractions
    from collections import Counter, defaultdict
    n = int(readline())
    a = [readline().rstrip("\n") for _ in range(n)]
    d = dict()
    ans = 0
    for x in a:
        fr = fractions.Fraction(x)
        num, den = fr.numerator, fr.denominator
        num_divs = enum_divisors(num)
        for div in num_divs:
            if d.get(div):
                c = d[div]
                ans += c[den]

        if not d.get(den):
            d[den] = Counter()
        d[den].update(num_divs)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
from decimal import Decimal

n = int(input())
a = [Decimal(input()) for _ in range(n)]
a = [i*10**9 for i in a]
MAX = 19
p_dict = collections.defaultdict(int)

for i in a:
    b_cnt = 0
    while i % 2 == 0 and b_cnt < 18:
        i //= 2
        b_cnt += 1
    f_cnt = 0
    while i % 5 == 0 and f_cnt < 18:
        i //= 5
        f_cnt += 1
    p_dict[(b_cnt, f_cnt)] += 1

ans = 0
for b1, f1 in p_dict:
    for b2, f2 in p_dict:
        if b1+b2 >= 18 and f1+f2 >= 18:
            if b1 == b2 and f1 == f2:
                ans += p_dict[(b1, f1)] * (p_dict[(b2, f2)] - 1)
            else:
                ans += p_dict[(b1, f1)] * p_dict[(b2, f2)]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N, *A = open(0).read().split()

S = [[0] * 21 for _ in range(21)]

ans = 0
for a in A:
    if (idx := a.find(".")) == -1:
        c2 = c5 = 0
    else:
        c2 = c5 = -(len(a) - idx - 1)

    a = int(a.replace(".", ""))
    while a % 2 == 0:
        c2 += 1
        a //= 2
    while a % 5 == 0:
        c5 += 1
        a //= 5
    c2 = min(c2, 10)
    c5 = min(c5, 10)
    ans += sum(S[i][j] for i in range(10 - c2, 21) for j in range(10 - c5, 21))

    S[c2 + 10][c5 + 10] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
numlist = [0] * (N + 1)
log2 = [0] * (N + 1)
log5 = [0] * (N + 1)
Ans = 0

for i in range(1,N+1):
  numlist[i] = float(input()) * 1000000000

  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 2 == 0:
      log2[i] += 1
      wk = wk // 2
    else:
      break
  
  wk = numlist[i]
  for cnt in range(1,19):
    if wk % 5 == 0:
      log5[i] += 1
      wk = wk // 5
    else:
      break
  
for i in range(1,N+1):
  for j in range(i+1,N+1):
    if log2[i] + log2[j] >= 18 and log5[i] + log5[j] >= 18:
      Ans += 1
  
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c = 0
j = 1
s = 0
for i in range (N):
    a = float(input()) * 10
    A.append(a)
for i in range (N - 1):
    for c in range (j):
        if (A[c] * A[j] / 100).is_integer() == True:
            s += 1
    j = j + 1
    i = 0
print(s)