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:
N = int(input())
A = []
c = 0
j = 1
s = 0
k = []
for i in range (N):
    a = float(input()) * 10
    A.append(a)
for i in range (N - 1):
    C = c
    for c in range (j):
        if (A[c] * A[j] / 100).is_integer() == True:
            s += 1
    j = j + 1
    i = 0
print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
from decimal import Decimal
N, *A = [Decimal(_) for _ in open(0).read().split()]
N = int(N)
c = [[0, 0] for _ in range(N)]
for i, a in enumerate(A):
    a = int(a * 10**9)
    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: Time Limit Exceeded

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(50)]

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,50):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)

Submission status: Time Limit Exceeded

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):
    lst1.append(int(Decimal(input())*(10**9)))

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

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,50):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [input() for i in range(n)]
from decimal import Decimal

#print(a)

li = []

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



ans = 0

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


for i in range(n):
    tmp = 0
    koron = 0
    for j in range(len(a[i])):
        if a[i][j] == '.':
            koron = j
        else:
            tmp = tmp*10+int(a[i][j])
        #print(tmp)
    if koron == 0:
        li.append(tmp)
    else:
        li.append(tmp/10**(len(a[i])-koron-1))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal,Inexact
from decimal import localcontext
n=int(input())
A=[Decimal(input()) for x in range(n)]
count=0
for i in range(1,n):
  for j in range(n-i):
    with localcontext() as ctx:
      ans=A[i-1]*A[i+j]
      ans.to_integral_exact()
      count += 1 if not ctx.flags[Inexact] else 0
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
  tmp=float(input())*10**9
  A.append(int(tmp))

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 or dev2>=18:
    dev2+=1
    A[i]//=2
  while A[i]%5==0 or 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: Time Limit Exceeded

Solution code:
from numpy import*
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)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# 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
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 = [Decimal(e)*1000000000 for e in a]
a = [Decimal(e) for e in a]
ret = 0
for i in range(N):
    for j in range(i):
        if a[i]*a[j] == int(a[i]*a[j]):
            #print(a[i],a[j],a[i]*a[j])
            ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
c=[[0]*50for _ in range(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: Time Limit Exceeded

Solution code:
from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = Decimal(input())
    d *= 10**9
    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: Time Limit Exceeded

Solution code:
from subprocess import*
c=[[0]*50for _ in range(50)]
r=0
for a in[*open(0)][1:]:
  a,b=map(run(('factor',str(round(float(a)*10**9))),stdout=PIPE).stdout.split().count,(b'2',b'5'))
  r+=sum(sum(d[max(0,18-b):])for d in c[max(0,18-a):])
  c[a][b]+=1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = Decimal(input())
    d *= 10**9
    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 a:
    for i , j in r.keys():
        if min(x+i,y+j) >= 18:
            ans += r[(i,j)]
            if x == i and y == j:
                ans -= 1
                
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
from decimal import Decimal

INF = 1 << 50



def run():
    N = int(sysread())
    A = [Decimal(input()) for _ in range(N)]
    M = [[0] * 19 for _ in range(19)]
    #print(A)
    minus = 0
    
    MULT = 10 ** 9
    for i, a in enumerate(A):
        if a == int(a):
            minus += 1
        a *= MULT
        a = int(a)
        
        #print(a)
        f2 = 0
        f5 = 0
        while True:
            if not a % 2:
                f2 += 1
                a = a // 2
            else:
                break
        while True:
            if not a % 5:
                f5 += 1
                a = a // 5
            else:
                break
        A[i] = (min(f2, 18), min(f5, 18))
        M[min(f2, 18)][min(f5, 18)] += 1

        
    #print(A)
    #for m in M:
    #    print(m)
    
    for i in range(18, -1, -1):
        for j in range(18, -1, -1):
            if i > 0:
                M[i-1][j] += M[i][j]
                
    for i in range(18, -1, -1):
        for j in range(18, -1, -1):
            if j > 0:
                M[i][j-1] += M[i][j]

    ans = 0
    for f2, f5 in A:
        ans += M[max(18-f2, 0)][max(18-f5, 0)]
        
    print((ans-minus)//2)
    
    #for m in M:
    #    print(m)
    

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    def divide2(x):
        num = 0
        while x % 2 == 0:
            x //= 2
            num += 1
        return num
    
    def divide5(x):
        num = 0
        while x % 5 == 0:
            x //= 5
            num += 1
        return num

    n = int(input())

    a = [[[] for _ in range(19)] for _ in range(10)]
    for _ in range(n):
        i = input()
        if '.' not in i:
            a[0][divide5(int(i))].append(divide2(int(i)))
        else:
            while i[-1] == '0':
                i = i[:len(i) - 1]
            if i[-1] == '.':
                i = i[:len(i) - 1]
                a[0][divide5(int(i))].append(divide2(int(i)))
            else:
                j = i.index('.')
                k = len(i) - j - 1
                a[k][divide5(int(i[:j] + i[j+1:]))].append(divide2(int(i[:j] + i[j+1:])))
    
    for i in range(10):
        for j in range(19):
            a[i][j].sort()
    
    def main2(a, b, n):
        if a == [] or b == []:
            return 0
        ans = 0
        for i in range(len(a)):
            j = 0
            while j < len(b) and a[i] + b[j] < n:
                j += 1
            ans += len(b) - j
        return ans

    ans = 0
    from itertools import combinations
    for i, j in combinations([0,1,2,3,4,5,6,7,8,9], 2):
        for k in range(19):
            if k > i + j:
                for l in range(19):
                    ans += main2(a[i][k], a[j][l], i + j)
            else:
                for l in range(i+j-k, 19):
                    ans += main2(a[i][k], a[j][l], i + j)

    num = 0
    for i in range(19):
        num += len(a[0][i])
    ans += num * (num - 1) // 2

    num = 0
    for i in range(1, 10):
        for k in range(19):
            if k > 2 * i:
                for l in range(19):
                    num += main2(a[i][k], a[i][l], 2 * i)
            else:
                for l in range(2*i - k, 19):
                    num += main2(a[i][k], a[i][l], 2 * i)
    ans += num // 2

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    def divide2(x):
        num = 0
        while x % 2 == 0:
            x //= 2
            num += 1
        return num
    
    def divide5(x):
        num = 0
        while x % 5 == 0:
            x //= 5
            num += 1
        return num

    n = int(input())

    a = [[[] for _ in range(20)] for _ in range(10)]
    for _ in range(n):
        i = input()
        if '.' in i:
            while i[-1] == '0':
                i = i[:len(i) - 1]
            if i[-1] == '.':
                i = i[:len(i) - 1]
        if '.' not in i:
            a[0][divide5(int(float(i)))].append(divide2(int(float(i))))
        else:
            j = i.index('.')
            k = len(i) - j - 1
            a[k][divide5(int(i[:j] + i[j+1:]))].append(divide2(int(i[:j] + i[j+1:])))
    
    for i in range(10):
        for j in range(20):
            a[i][j].sort()
    
    def main2(a, b, n):
        if a == [] or b == []:
            return 0
        ans = 0
        for i in range(len(a)):
            j = 0
            while j < len(b) and a[i] + b[j] < n:
                j += 1
            ans += len(b) - j
        return ans

    ans = 0
    from itertools import combinations
    for i, j in combinations([0,1,2,3,4,5,6,7,8,9], 2):
        for k in range(20):
            if k > i + j:
                for l in range(20):
                    ans += main2(a[i][k], a[j][l], i + j)
            else:
                for l in range(i+j-k, 20):
                    ans += main2(a[i][k], a[j][l], i + j)

    num = 0
    for i in range(20):
        num += len(a[0][i])
    ans += num * (num - 1) // 2

    num = 0
    for i in range(1, 10):
        for k in range(20):
            if k > 2 * i:
                for l in range(20):
                    num += main2(a[i][k], a[i][l], 2 * i)
            else:
                for l in range(2*i - k, 20):
                    num += main2(a[i][k], a[i][l], 2 * i)
    ans += num // 2

    print(ans)

main()

Submission status: Time Limit Exceeded

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

# A - Integer Product
from decimal import Decimal

N = int(input())
A = []

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

ans = 0

for i in range(N - 1):
	for j in range(i + 1, N):
		product = A[i] * A[j]		

		if product == int(product):
			ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Integer Product
from decimal import Decimal

N = int(input())
A = []

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

ans = 0

for i in range(N - 1):
	for j in range(i + 1, N):
		product = A[i] * A[j]		

		if product == int(product):
			ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Integer Product
from decimal import Decimal
from itertools import combinations

N = int(input())
A = []

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

combis = list(combinations(A, 2))
ans = 0

for c in combis:
	product = c[0] * c[1]
	
	if product == int(product):
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Integer Product 
from decimal import Decimal

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

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
# A - Integer Product 
from decimal import Decimal

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

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%2 == 0):
    c += 1
    bi //= 2
  p2[i] = c
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%5 == 0):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(50)] for _ in range(50)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(48,-1,-1):
  for j in range(48,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[max(18-p2[i],0)][max(18-p5[i],0)]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

nums = [float(input()) for _ in range(N)]

two_fives = []


for i, num in enumerate(nums):
    int_converted = int(num * (10**9))
    
    two_div_count = 0
    while int_converted % 2 == 0:
        two_div_count += 1
        int_converted //= 2
        
    
    five_div_count = 0
    while int_converted % 5 == 0:
        five_div_count += 1
        int_converted //= 5

    two_fives.append((two_div_count,five_div_count))


ok_count = 0
for i in range(N):
    for j in range(i+1,N):
        two_sum = two_fives[i][0] + two_fives[j][0]
        five_sum = two_fives[i][1] + two_fives[j][1]
        if two_sum >= 18 and five_sum >= 18:
            ok_count += 1

print(ok_count)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

Submission status: Time Limit Exceeded

Solution code:
import sys
eps = sys.float_info.epsilon

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

ans = 0
for i in range(N):
    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:
""" 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

    p9 = pow(10, 9)
    p18 = pow(10, 18)

    for i in range(0, _N):
        for j in range(i+1, _N):
            Ai_0 = int(A[i])
            Ai_1 = int(A[i] * p9) % p9
            Aj_0 = int(A[j])
            Aj_1 = int(A[j] * p9) % p9

            C = (
                (Ai_0 * Aj_1) % p9 * p9 \
                + (Aj_0 * Ai_1) % p9 * p9 \
                + (Ai_1 * Aj_1) % p18
            ) % p18

            if C == 0:
                count += 1

    return count

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

    print(main(_N, _A))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(19)] for _ in range(19)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 19):
        for k in range(rem2, 19):
            ans += plot[j][k]
    plot[min(18, d25[1])][min(18, d25[0])] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

a = []
for _ in range(n):
    aa = input().split('.')
    aaa = int(aa[0])*10**9
    if len(aa) == 2:
        aaa += int(aa[1])*10**(9-len(aa[1]))
    a2, a5 = 0, 0
    while aaa % 2 == 0:
        a2 += 1
        aaa = aaa // 2
    while aaa % 5 == 0:
        a5 += 1
        aaa = aaa // 5
    a.append([a2, a5])

na = np.array(a)

ans = 0
for i, aa in enumerate(a):
    ans += np.count_nonzero((na[i+1:, 0] >= 18-aa[0]) & (na[i+1:, 1] >= 18-aa[1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
import numpy as np
def main(n,a):
  k=60
  mp=np.zeros((k,k),np.int32)
  o=k//2
  ary=[]
  for i in range(n):
    b=list(a[i].split('.'))
    b.append('0')
    x=int(b[0])
    y=int((b[1]+'0'*9)[:9])
    x=x*pow(10,9)+y
    # x10^9
    cnt5=-9
    xx=x
    while xx>1:
      if xx%5==0:
        cnt5+=1
        xx//=5
      else:
        break
    cnt2=-9
    xx=x
    while xx>1:
      if xx%2==0:
        cnt2+=1
        xx//=2
      else:
        break
    #if 0<=cnt5+o<23 and 0<=cnt2+o<23:
    mp[cnt5+o,cnt2+o]+=1
    ary.append([cnt5+o,cnt2+o])

  ans=0
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[j][i-1]+=mp[j][i]
  for i in range(k-1,0,-1):
    for j in range(k):
      mp[i-1][j]+=mp[i][j]
  for x,y in ary:
    if x>=o and y>=o:
      i=1
    else:
      i=0
    x-=o
    x*=-1
    x+=o
    y-=o
    y*=-1
    y+=o
    ans+=mp[x,y]-i
  print(ans//2)
  #mp[o,o]+=10
  #print(mp)

n=int(input())
a=np.array([input() for _ in range(n)])
main(n,a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(45)] for _ in range(20)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 20):
        for k in range(rem2, 45):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(50)] for _ in range(25)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 25):
        for k in range(rem2, 50):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit, i4, i8


@njit(i4(i8, i4), cache=True)
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input())*10**9)
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input())*10**9)
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = [round(float(input()) * pow(10, 9)) for _ in range(n)]
arr2 = [div(x, 2) for x in arr]
arr5 = [div(x, 5) for x in arr]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr2[i] + arr2[j] >= 18 and arr5[i] + arr5[j] >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = [round(float(input()) * 10**9) for _ in range(n)]
arr2 = [div(x, 2) for x in arr]
arr5 = [div(x, 5) for x in arr]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr2[i] + arr2[j] >= 18 and arr5[i] + arr5[j] >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
 
N=int(input())
a=[input() for x in range(N)]
count=0
 
for number in a:
	for numbers in a:
		if number<numbers:
			i=float(number)*float(numbers)
			j=math.ceil(float(number)*float(numbers))
			if i%j==0:
				count+=1
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = [int(float(input()) * 10**9) % 10**18 for i in range(n)]

answer = 0

for i in range(n-1):
    for j in range(i+1,n):
        x = a[i] * a[j]
        if x % 10**18 == 0:
            answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

d = {}
for a in A:
    a = int(a * (10 ** 9))
    x = -9
    while a % 2 == 0:
        x += 1
        a %= 2
    y = -9
    while a % 5 == 0:
        y += 1
        a %= 5
    t = (x, y)
    d.setdefault(t, 0)
    d[t] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from decimal import Decimal
n = int(input())
a = [int(Decimal(input()) * (pow(10, 9))) for i in range(n)]
l = [[0] * 19 for i in range(19)]
ans = 0
for i in a:
    cnt2 = 0
    i2 = deepcopy(i)
    while i2 % 2 == 0 and cnt2 < 18:
        i2 //= 2
        cnt2 += 1
    cnt5 = 0
    i5 = deepcopy(i)
    while i5 % 5 == 0 and cnt5 < 18:
        i5 //= 5
        cnt5 += 1
    ans += l[19 - cnt2 - 1][19 - cnt5 - 1]
    for i in range(cnt2 + 1):
        for j in range(cnt5 + 1):
            l[i][j] += 1
print(ans)