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 numpy as np
from numba import njit, i4, i8


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


@njit(i8(i8[:, :], i8), cache=True)
def solve(arr, length):
    ans = 0
    for i in range(length):
        for j in range(i + 1, length):
            a, b, c, d = arr[0][i], arr[1][i], arr[0][j], arr[1][j]
            if a + c >= 18 and b + d >= 18:
                ans += 1
    return ans


n = int(input())
arr = np.array([input() for _ in range(n)], np.float64)
arr = np.rint(arr * 10**9).astype(np.int64)

f = np.vectorize(div)
arr = np.vstack([f(arr, 2), f(arr, 5)])

print(solve(arr, arr.shape[1]))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal

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

cnt = 0
for i in range(1, n):
    for j in range(n - i):
        ans = A[i - 1] * A[i + j]
        if ans == ans.to_integral_value():
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
A2 = []
A5 = []
for i in range(N):
    a=input()
    tmp = int(a.replace('.', ''))
    count2 = 0
    count5 = 0
    for _ in range(18):
        if tmp % 2 == 0:
            count2 += 1
            tmp /= 2
        else:
            break
    for _ in range(18):
        if tmp % 5 == 0:
            count5 += 1
            tmp /= 5
        else:
            break
    if a.find('.') > 0:
        count2 += 10 - len(a) + a.find('.')
        count5 += 10 - len(a) + a.find('.')
    else:
        count2 += 9
        count5 += 9
    A2.append(count2)
    A5.append(count5)
ans=0
for i in range(N):
    for j in range(i+1,N):
        if A2[i] + A2[j] >= 18 and A5[i] + A5[j] >= 18:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
from numba import njit, i4, i8


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

    @njit(cache=True)
    def solve(arr):
        ans = 0
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                (a, b), (c, d) = arr[i], arr[j]
                if a + c >= 18 and b + d >= 18:
                    ans += 1
        return ans

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

    print(solve(arr))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
from numba import njit, i4, i8


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


@njit(cache=True)
def solve(arr):
    ans = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            (a, b), (c, d) = arr[i], arr[j]
            if a + c >= 18 and b + d >= 18:
                ans += 1
    return ans


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

print(solve(arr))

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
from numba import njit, i4, i8


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


@njit(cache=True)
def solve(arr):
    ans = 0
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            (a, b), (c, d) = arr[i], arr[j]
            if a + c >= 18 and b + d >= 18:
                ans += 1
    return ans


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

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
from numba import njit, i4, i8


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


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

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit


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


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

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal


def div(n):
    n = int(n)
    two = format(n, 'b')[::-1].find('1')
    if two < 0:
        return(-1, -1)
    n = n >> two
    cnt = 0
    while n % 5 == 0:
        n //= 5
        cnt += 1
    return (two, cnt)


n = int(input())
arr = [div(int(Decimal(input()) * 10**9)) for _ in range(n)]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal

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

num=[aa.numerator*10**9//aa.denominator for aa in a]

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

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,45):
        for cc5 in range(18-c5,20):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

N = int(input())

A = [Decimal(input()) for i in range(N)]

nanachi = [[0, 0] for i in range(N)]

eprint(A)

def is_integer(n: Decimal):
  return n == n.to_integral_value()

for i, a in enumerate(A):
  t = 0
  while not is_integer(a):
    a *= 10
    t += 1
  nanachi[i][0] = -t
  nanachi[i][1] = -t
  while a % 2 == 0:
    a = a / 2
    nanachi[i][0] += 1
  while a % 5 == 0:
    a = a / 5
    nanachi[i][1] += 1

eprint(nanachi)

tmp = min(map(min, nanachi))

for i in range(N):
  nanachi[i][0] -= tmp
  nanachi[i][1] -= tmp

eprint(nanachi)

aaa = [[0] * 200 for i in range(200)]

for a in nanachi:
  aaa[a[0]][a[1]] += 1

acc = [[0] * 201 for i in range(201)]

for i in reversed(range(0, 200)):
  for k in reversed(range(0, 200)):
    acc[i][k] = acc[i+1][k] + acc[i][k+1] - acc[i+1][k+1] + aaa[i][k]

res = 0

for a in nanachi:
  i = max(0, - (a[0] + 2*tmp))
  k = max(0, - (a[1] + 2*tmp))
  res += acc[i][k]
  if a[0] >= -tmp and a[1] >= -tmp:
    res -= 1

res = res // 2

print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal

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

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*40 for _ in range(40)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,40):
        for cc5 in range(18-c5,40):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal
from collections import deque
n = int(input())
a = [Decimal(input()) for _ in range(n)]
res = 0
bdr = Decimal(str(1e-5))
for i,j in enumerate(a):
  if (j!=j//1) and bdr-(j-j//1)>0:
    continue
  for k in a[i+1:]:
    tmp = j*k
    if tmp-tmp//1 < 1e-19:
      res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal

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

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,50):
        for cc5 in range(18-c5,50):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
def main():
  n=int(input())
  a=[]
  b=[]
  c=[]
  z=0
  for i in range(n):
    tempa=input().split(".")
    if(len(tempa)==1):
      z=z+1
      tempa=int(tempa[0])
      if (tempa % 2) == 0  or (tempa % 5) == 0:
        a.append(int(tempa))
    else:
      ta=int(tempa[1])
      if ta==0:
        z=z+1
        tempa=int(tempa[0])
        if (tempa % 2) == 0  or (tempa % 5) == 0:
          a.append(int(tempa))
      else:
        b.append(int("".join(tempa)))
        c.append(10**len(tempa[1]))
  nz=n-z
  r=z*(z-1)//2
  #a=np.array(a)
  #b=np.array(b)
  #c=np.array(c)
  fz=0
  z=len(a)
  for j in range(z):
    for k in range(nz):
      tempd=a[j]*b[k]
      if (tempd % c[k]) ==0:
        fz=fz+1
  for j in range(nz-1):
    tempd=c[j]
    tempe=b[j]
    for k in range(j+1,nz):
      tempb=tempe*b[k]
      tempc=tempd*c[k]
      if (tempb % tempc) ==0:
        fz=fz+1
  print(r+fz)
main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal
n=int(input())
xx=[]
yy=[]
r=0
for i in range(n):
  p=float(input())
  p=p*1000000000
  p=int(p)
  p=Fraction(p,1000000000)
  xx.append(p.numerator)
  yy.append(p.denominator)
  
for k in range(n):
  x=xx[k]
  y=yy[k]
  for m in range(n-k-1):
    l=x%yy[k+m+1]
    l=l+xx[k+m+1]%y
    if l==0:
      r=r+1
print(r)

Submission status: Time Limit Exceeded

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

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret={x}
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal
n=int(input())
a=[]
r=0
for i in range(n):
  p=float(input())
  p=p*1000000000
  p=int(p)
  p=Fraction(p,1000000000)
  a.append(p)
  
for k in range(n):
  x=a[k].numerator
  y=a[k].denominator
  for m in range(n-k-1):
    l=x%a[k+m+1].denominator
    l=l+a[k+m+1].numerator%y
    if l==0:
      r=r+1
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import decimal
a = [decimal.Decimal(input()) for i in range(N)]
count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            if a[i]-int(a[i])==0 and a[j]-int(a[j])==0:
                count += 1
                continue
            kakeru = a[i]*a[j]
            if kakeru - int(kakeru) == 0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

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

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret={x}
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A2 = []
dic = {}


for i in range(1, N+1):
  A = input()
  x2 = 0
  x5 = 0
  y = 0
  buf = [0, 0, 0]
  j = 0
  l = len(A)
  for a in A[::-1]:
    if a == ".":
      buf[2] = j
      A = A[:l-j-1] + A[l-j:]
      y = j
      break
    j += 1
    if j > 9:
      break
  A = int(A)
  j = 0
  B = A
  while B%2==0:
    j += 1
    B = B//2
  buf[0] = j
  x2 = j
  j = 0
  B = A
  while B%5==0:
    j += 1
    B = B//5
  buf[1] = j
  x5 = j
  A2.append(buf)
  if x2-y not in dic:
    dic[x2-y] = {}
  if x5-y not in dic[x2-y]:
    dic[x2-y][x5-y] = 0
  dic[x2-y][x5-y] += 1

for x in dic:
  buf = sorted(dic[x].items(), reverse = True)
  dic[x] = {}
  for key, value in buf:
    dic[x][key] = value

buf = sorted(dic.items(), reverse = True)
dic = {}
for key, value in buf:
  dic[key] = value

#print(dic)

ans = 0
i = -1
for x, y, z in A2:
  i += 1
  x1 = x-z
  y1 = y-z
  if dic[x1][y1] > 1:
    dic[x1][y1] -= 1
  else:
    dic[x1].pop(y1)
  
  for x2 in dic.keys():
    if x2 < -x1:
      break
    for y2 in dic[x2].keys():
      #print(A2[i], x2, y2, x1, y1)
      if y2 < -y1:
        break
      ans += dic[x2][y2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from decimal import Decimal

number_set = list()
i = 1
u = 0
y = 0

a = int(input())
while i <= a:
    number_set.append(Decimal(input()))
    i += 1

for pair in itertools.combinations(number_set, 2):
    y = pair[0] * pair[1]
    if y - int(y) == 0:
        u += 1


print(u)

Submission status: Time Limit Exceeded

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

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret=set()
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    answer+=div_dic2[(bumbo,d)]
    
  for d in div_set:    
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
  n = int(input())
  a = [float(input()) for _ in range(n)]
  
  ans = 0
  count = 0
  
  for i in range(n):
    listJ = list(range(i + 1, n))
    for j in listJ:
      ans = 0.01 * (a[i]*10) * (a[j]*10)
      if ans - int(ans) == 0:
        count += 1
  print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
An = [list(map(float,input().split())) for i in range(n)]

cnt = 0
for i in range(n-1):
    t = int(An[i][0]*10**9)
    if t < 10**5:
        continue
    for j in range(i+1,n):
        s = int(An[j][0]*10**9)
        mul = t*s
        if mul%10**18 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from decimal import Decimal

number_set = list()
result_set = list()
i = 1
u = 0
y = 0

a = int(input())
while i <= a:
    number_set.append(Decimal(input()))
    i += 1

for pair in itertools.combinations(number_set, 2):
    result_set.append(pair[0] * pair[1])

    
for re in result_set:
    if re-int(re) == 0:
        u += 1
        
print(u)

Submission status: Time Limit Exceeded

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

div2 = [0 for i in range(N)]
div5 = [0 for i in range(N)]

for i in range(N):
    tmp = A[i]
    while tmp % 2 == 0:
        div2[i] += 1
        tmp = tmp//2
    while tmp % 5 == 0:
        div5[i] += 1
        tmp = tmp//5

cnt = [[0 for i in range(19)] for i in range(19)]

for i in range(N):
    d2 = div2[i]
    d5 = div5[i]
    if d2 > 18:
        d2 = 18
    if d5 > 18:
        d5 = 18
    cnt[d2][d5] += 1

ans = 0

for i in range(N):
    lower2 = 18 - div2[i]
    lower5 = 18 - div5[i]

    if lower2 < 0:
        lower2 = 0
    if lower5 < 0:
        lower5 = 0

    for j in range(lower2, 19):
        for k in range(lower5, 19):
            ans += cnt[j][k]

for a in A:
    if a % P == 0:
        ans -= 1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
  n = int(input())
  a = [float(input()) for _ in range(n)]
  
  ans = 0
  count = 0
  
  for i in range(n):
    listJ = list(range(i + 1, n))
    for j in listJ:
      ans = (a[i]*10) * (a[j]*10)
      ans = ans*0.01
      if ans - int(ans) == 0:
        count += 1
  print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
from decimal import Decimal
n=int(input())
a=[]
r=0
for i in range(n):
  p=float(input())
  p=p*1000000000
  p=int(p)
  p=Fraction(p,1000000000)
  a.append(p)
for k in range(n):
  for m in range(n-k-1):
    #x=Fraction(Decimal(a[k]))
    #y=Fraction(Decimal(a[k+m+1]))
    l=a[k]*a[k+m+1]
    
    if l.denominator==1:
      r=r+1
      
      
print(r)

Submission status: Time Limit Exceeded

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

div_dic=defaultdict(int)
def add_fact(x):
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      div_dic[i]+=1
      if i!=x//i:
        div_dic[x//i]+=1
  return

alist=[]
int_list=[]
for _ in range(N):
  a=input()
  if "." in a:
    seisu,shosu=a.split(".")
    seisu=int(seisu)
    shosu=int(shosu.ljust(9,'0'))
    
    bunshi=10**9*seisu+shosu
    bumbo=10**9
    gcd_bb=math.gcd(bunshi,bumbo)
    bunshi//=gcd_bb
    bumbo//=gcd_bb
    
    if bumbo==1:
      int_list.append(bunshi)
      add_fact(bunshi)
    else:
      alist.append((bunshi,bumbo))
  else:
    seisu=int(a)
    int_list.append(seisu)
    add_fact(seisu)
#print(int_list,alist,div_dic)

num_int=len(int_list)
answer=num_int*(num_int-1)//2
for bunshi,bumbo in alist:
  answer+=div_dic[bumbo]

#shosudoshi
def set_fact(x):
  ret=set()
  for i in range(1,int(x**0.5)+1):
    if x%i==0:
      ret.add(i)
      ret.add(x//i)
  return ret

#print(alist)
div_dic2=defaultdict(int)
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)
  #print(div_set,bumbo)
  for d in div_set:
    #print(d,bumbo)
    div_dic2[(d,bumbo)]+=1
#print(div_dic2)
  
answer2=0
for bunshi,bumbo in alist:
  div_set=set_fact(bunshi)  
  for d in div_set:    
    #print(bunshi,d)
    answer2+=div_dic2[(bumbo,d)]

#print(answer,answer2)
print(answer+answer2//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
import numpy as np
from collections import deque
from decimal import Decimal
import math

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

    N=int(input())
    A=[]
    d=[0]*N #少数点以下の桁数
    two=[0]*N #２で割れる回数
    five=[0]*N  #5で割れる回数
    p_t=[]
    m_t=[]
    p_f=[]
    m_f=[]

    for i in range(N):
        tmp=input()
        d_A=Decimal(tmp)
        split=list(tmp.split('.'))
        if len(split)==2:
            d[i]=len(str(Decimal('0.'+split[1])))-1
            # print('split[1]=',split[1],' str=',str(Decimal(split[1])))
        int_d_A=d_A*(10**d[i])
        while int_d_A%2==0:
            int_d_A//=2
            two[i]+=1
        while int_d_A%5==0:
            int_d_A//=5
            five[i]+=1
        # print(split)
        A.append(d_A)
        # print('num=',tmp,' d=',d[i],' two=',two[i],' five=',five[i])

        two[i]-=d[i]    #余ってる数
        five[i]-=d[i]
        if two[i]>=0:
            p_t.append(i)
        else:
            m_t.append(i)
        if five[i]>=0:
            p_f.append(i)
        else:
            m_f.append(i)

    ans=0
    for i in range(N):
        if two[i]<=0 and five[i]<=0:
            for j in set(p_t) & set(p_f):
                if j>i and two[i]+two[j]>=0 and five[i]+five[j]>=0:
                    ans+=1
                    # print('A[i]=',A[i],' A[j]=',A[j])
        elif two[i]<0 and five[i]>=0:
            for j in set(p_t):
                if j>i and two[i]+two[j]>=0 and five[i]+five[j]>=0:
                    ans+=1
                    # print('A[i]=',A[i],' A[j]=',A[j])
        elif two[i]>=0 and five[i]<0:
            for j in set(p_f):
                if j>i and two[i]+two[j]>=0 and five[i]+five[j]>=0:
                    ans+=1
                    # print('A[i]=',A[i],' A[j]=',A[j])
        else:
            for j in range(i+1,N):
                if j>i and two[i]+two[j]>=0 and five[i]+five[j]>=0:
                    ans+=1
                    # print('A[i]=',A[i],' A[j]=',A[j])


    # for n in list(itertools.combinations(list(range(N)),2)):
    #     if two[n[0]]+two[n[1]]>=0 and five[n[0]]+five[n[1]]>=0:
    #         ans+=1


    # for i in range(N-1):
    #     for j in range(i+1, N):
    #         # if (A[i]*A[j])%1==0:
    #         if min(two[i] + two[j], five[i] + five[j]) >= d[i] + d[j]:
    #             # print('two=',two[i] + two[j],' five=',five[i] + five[j], 'd=',d[i] + d[j])
    #             # print('A[i]=',A[i],' A[j]=',A[j],' A[i]*A[j]=',A[i]* A[j])
    #             ans+=1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
  n = int(input())
  a = [float(input()) for _ in range(n)]
  
  ans = 0
  count = 0
  
  for i in range(n):
    listJ = list(range(i + 1, n))
    for j in listJ:
      if isinstance(a[i], int) and isinstance(a[j], int):
        count += 1
      else:
        ans = (a[i]*10) * (a[j]*10)
        ans = ans*0.01
      if ans - int(ans) == 0:
        count += 1
  print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
D = defaultdict(lambda:defaultdict(int))
for j in range(n):
    a = Decimal(input())
    cnt1 = 0
    cnt2 = 0
    while a % 1:
        a *= 10
        cnt1 -= 1
        cnt2 -= 1
    while a % 2 == 0:
        a /= 2
        cnt1 += 1
    while a % 5 == 0:
        a /= 5
        cnt2 += 1
    D[cnt1][cnt2] += 1

ans = 0
for i in range(-15, 20):
    for k in range(-15, 25):
        for j in range(-10, 12):
            for l in range(-10, 12):
                if i + k >= 0 and j + l >= 0:
                    if i == k and j == l:
                        ans += D[i][j] * (D[k][l] - 1)
                    else:
                        ans += D[i][j] * D[k][l]

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
def main():
  n=int(input())
  a=[]
  b=[]
  c=[]
  z=0
  for i in range(n):
    tempa=input().split(".")
    if(len(tempa)==1):
      z=z+1
      tempa=int(tempa[0])
      if (tempa % 2) == 0  or (tempa % 5) == 0:
        a.append(int(tempa))
    else:
      ta=int(tempa[1])
      if ta==0:
        z=z+1
        tempa=int(tempa[0])
        if (tempa % 2) == 0  or (tempa % 5) == 0:
          a.append(int(tempa))
      else:
        b.append(int("".join(tempa)))
        c.append(10**len(tempa[1]))
  nz=n-z
  r=z*(z-1)//2
  #a=np.array(a)
  #b=np.array(b)
  #c=np.array(c)
  fz=0
  z=len(a)
  for j in range(z):
    for k in range(nz):
      tempd=a[j]*b[k]
      if (tempd % c[k]) ==0:
        fz=fz+1
  for j in range(nz-1):
    for k in range(j+1,nz):
      tempb=b[j]*b[k]
      tempc=c[j]*c[k]
      if (tempb % tempc) ==0:
        fz=fz+1
  print(r+fz)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
D = defaultdict(lambda:defaultdict(int))
for j in range(n):
    a = Decimal(input())
    cnt1 = 0
    cnt2 = 0
    while a % 1:
        a *= 10
        cnt1 -= 1
        cnt2 -= 1
    while a % 2 == 0:
        a /= 2
        cnt1 += 1
    while a % 5 == 0:
        a /= 5
        cnt2 += 1
    D[cnt1][cnt2] += 1

ans = 0
for i in range(-15, 20):
    for k in range(-15, 25):
        for j in range(-12, 13):
            for l in range(-12, 13):
                if i + k >= 0 and j + l >= 0:
                    if i == k and j == l:
                        ans += D[i][j] * (D[k][l] - 1)
                    else:
                        ans += D[i][j] * D[k][l]

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
from decimal import Decimal 
from sys import stdin
import math

input = stdin.readline
def fac(n: int):
    if n <= 1:
        return 0
    elif n == 2:
        return 1
    else:
        return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

def main():
    N = int(input().rstrip())
    A = []
    B = []
    for _ in range(N):
        t = Decimal(input().rstrip())
        if t == t.to_integral_value():
            B.append(t)
        else:
            A.append(t)
    
    ans = fac(len(B))
    for i, a in enumerate(A, 1):
        for aa in A[i:] + B:
            p = aa * a
            if p == p.to_integral_value():
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from decimal import Decimal

number_set = list()
result_set = list()
i = 1
u = 0

a = int(input())
while i <= a:
    number_set.append(Decimal(input()))
    i += 1

for pair in itertools.combinations(number_set, 2):
    z = (pair[0] * pair[1])-int((pair[0] * pair[1]))
    if z == 0:
        u += 1

print(u)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
n=int(input())
a=[]
c=0
for i in range(n):
	a.append((input()))
	c += len([1 for i in range(len(a)-1) if Decimal(a[i])*Decimal(a[-1])==int(Decimal(a[i])*Decimal(a[-1]))])
# print(len([1 for i in range(len(a)) for j in range(i, len(a)) if i<j and Decimal(a[i])*Decimal(a[j])==int(Decimal(a[i])*Decimal(a[j]))]))
print(c)