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: Runtime Error

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

# import numpy as np

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

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


# ===CODE===
def prime_factorize(n):
    two = 0
    five = 0
    while n % 2 == 0:
        two += 1
        n //= 2

    while n % 5 == 0:
        five += 1
        n //= 5

    return two, five


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

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

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

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

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

    print(ans // 2)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
ans = 0
ls = []
for i in range(n):
  l = float(input())
  ls = ls + [l]

for i in range(n):
  for j in range(n):
    if l[i] >= l[j]:
      continue
    elif ((ls[i])*(ls[j]))%1 == 0:
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

for i in range(n):
    s = input()
    x = s.find('.')
    if x == -1:
        s = s + '0'*9
    else:
        s = s.replace('.','') + '0'*(10-(len(s)-x))
    s = int(s)
    d2 = 0
    d5 = 0
    for _ in range(20):
        if s%2 == 0:
            s = s//2
            d2 += 1
        else:
            break
    for _ in range(20):
        if s%5 == 0:
            s = s//5
            d5 += 1
        else:
            break
    dp[d2][d5] += 1
    dq[d2][d5] += 1

for i in range(19,-1,-1):
    for j in range(19,0,-1):
        dp[i][j-1]+=dp[i][j]
for j in range(19,-1,-1):
    for i in range(19,0,-1):
        dp[i-1][j]+=dp[i][j]
ret = 0
for i in range(18):
    for j in range(18):
        ret += dq[i][j] * dp[18-i][18-j]
ret -= dp[9][9]
print(ret//2)

Submission status: Runtime Error

Solution code:
"""
小数の状態だと処理しづらいので、与えられた数を全て10**9倍して小数を確実になくした上で
問題文を下記のように言い換える。
「積が10**18の倍数になるような数の組み合わせの数がいくつあるか」
数Aiがあり、Aiの2の素因数の数がn, 5の素因数の数がmのとき、
数Ai自体ですでにmin(n,m)個の0の数を持っている。この場合、のこり必要な0の数はx = 18-min(n,m)個である。
ここで、n == mの場合：
Aiの相方は少なくとも2,5の素因数をそれぞれx個以上持っていなくてはならない。
n > mの場合：
Aiの相方は少なくとも2の素因数をx-(n-m)個、5の素因数をx個持っていなくてはいけない。

m > nの場合：
Aiの相方は少なくとも2の素因数をx個以上、5の素因数をx-(m-n)個以上持っていなくてはならない。
"""
N = int(input())
dp = [[0]*(19) for _ in range(19)]
ans = 0
for _ in range(N):
    a = float(input())
    a *= 10**9
    two = 0
    while a % 2 == 0:
        a //= 2
        two += 1
    five = 0
    while a % 5 == 0:
        a //= 5
        five += 1

    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: Runtime Error

Solution code:
import numpy as np

N = int(input())

A = []
for i in range(N):
    num = float(input()) * 10000
    if float.is_integer(num):
        A.append(int(num))


def count2(n):
    ret = 0
    while(n % 2 == 0):
        ret += 1
        n /= 2
    return ret


def count5(n):
    ret = 0
    while(n % 5 == 0):
        ret += 1
        n /= 5
    return ret


table = {}
for i in range(9):
    for j in range(9):
        table[i, j] = 0

for a in A:
    c2 = count2(a)
    c5 = count5(a)
    if(c2 > 8):
        c2 = 8
    if(c5 > 8):
        c5 = 8
    for i in range(c2 + 1):
        for j in range(c5 + 1):
            table[i, j] += 1

res = 0
for a in A:
    pair = count2(a), count5(a)
    t, f = pair
    res += table[8 - t, 8 - f]
    if t >= 4 and f >= 4:
        res -= 1

print(res // 2)

Submission status: Runtime Error

Solution code:
AS= input()
a = tuple(S)
#print(a)
#print(a[0])

cou = 1
for i in range (0,len(S)-1):
    
    if a[i] == "R":
      if a[i+1] != "S":
          cou+=1
if a[0] == "S":
    cou=0
    #elif a[i]=="S":
     #   cou=0
print(cou)

Submission status: Runtime Error

Solution code:
n=int(input())
pairs=0
for i in range(0,n):
  x=int(input())
  
list_s=list(n) 
if(list_s[i]<list_s[i+1]):
  count+=1
 
print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
pairs=0
for i in range(0,n):
  x=int(input())
  
  
 if(n[i]<n[i+1]):
  count+=1
  
 print(count)

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
A = list(map(float,input().split()))
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)

return count

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
A = list(map(int,input().split()))
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)

return count

Submission status: Runtime Error

Solution code:
import copy

N = int(input())
A = list(map(int,input().split()))
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)

return count

Submission status: Runtime Error

Solution code:
count = 0
N = input()
for i in N:
  a = input()
  b = input()
  if isinstance(a*b,int):
  	count++
 
print(count)

Submission status: Runtime Error

Solution code:
MOD = 1000000007
from collections import defaultdict as dd,Counter,deque

def si(): return input()
def ii(): return int(input())
def li(): return list(map(int,input().split()))
def mi(): return map(int,input().split())
def out(v): print(v)
def spout(): print(v,end=" ")
def d2b(n): return bin(n).replace("0b","")
def twod(n,m,num):return [[num for x in range(m)] for y in range(n)]
def vow(): return ['a','e','i','o','u']
def let(): return [chr(i) for i in range(97,123)]
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
def ispow2(x):
    return (x and (not(x & (x - 1))))
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i: i+=1
        else:
            n //= i
            factors.append(i)
    if n > 1: factors.append(n)
    return (list(factors))
  
n=ii()
a=[]
while n:
  n-=1
  a.append(float(input))
c=0
for i in range(n):
  for j in range(i+1,n):
    if (a[i]*a[j]).is_integer(): c+=1
print(c)

Submission status: Runtime Error

Solution code:
import copy
n = int(input())
def point_shift(s,i):
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

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

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]

ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = 18-x0,18-y0
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)

Submission status: Runtime Error

Solution code:
n = int(input())
dic = {}
for i in range(45):
  for j in range(20):
    dic[[i, j]] = 0
for _ in range(n):
  a = float(input())
  a *= 10**9
  idx_2 = 0
  while a % 2 == 0:
    a //= 2
    idx_2 += 1
  idx_5 = 0
  while a % 5 == 0:
    a //= 5
    idx_5 += 1
  dic[[idx_2, idx_5]] += 1
  
lst = []
for k, v in dic.items():
  lst.append([k[0], k[1], v])

cnt = 0
for i in range(len(lst)):
  for j in range(i, len(lst)):
    a, b, c = lst[i][0], lst[i][1], lst[i][2]
    d, e, f = lst[j][0], lst[j][1], lst[j][2]
    if a + d >= 18 and b + e >= 18 and j == i:
      cnt += (c * (c - 1)) // 2
    elif a + d >= 18 and b + e >= 18:
      cnt += c * f
print(cnt)

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return a[i][j]+a[arg][j] >= 0

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
a = [[0]*25 for i in range(25)]
for i in range(n):
    A = int(float(input())*10**9)
    m2 = m5 = 0
    while A % 10 == 0:
        A //= 10
        m2 += 1
        m5 += 1
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    a[m2][m5] += 1

ans = 0
for i in range(25):
    for j in range(25):
        if a[i][j] > 0:
            for k in range(25):
                for l in range(25):
                    if i + k >= 18 and j + l >= 18:
                        if i == k and j == l:
                            ans += a[i][j] * ( a[k][l] - 1 )
                        else:
                            ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return a[i][j]+a[arg][j] >= 0

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
a = [[0]*20 for i in range(20)]
for i in range(n):
    A = int(float(input())*10**9)
    m2 = m5 = 0
    while A % 10 == 0:
        A //= 10
        m2 += 1
        m5 += 1
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    a[m2][m5] += 1

ans = 0
for i in range(20):
    for j in range(20):
        if a[i][j] > 0:
            for k in range(20):
                for l in range(20):
                    if i + k >= 18 and j + l >= 18:
                        if i == k and j == l:
                            ans += a[i][j] * ( a[k][l] - 1 )
                        else:
                            ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return a[i][j]+a[arg][j] >= 0

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
a = [[0]*15 for i in range(15)]
for i in range(n):
    A = int(float(input())*10**9)
    m2 = m5 = 0
    while A % 10 == 0:
        A //= 10
        m2 += 1
        m5 += 1
    while A % 2 == 0:
        A //= 2
        m2 += 1
    while A % 5 == 0:
        A //= 5
        m5 += 1
    a[m2][m5] += 1

ans = 0
for i in range(15):
    for j in range(15):
        if a[i][j] > 0:
            for k in range(15):
                for l in range(15):
                    if i + k >= 18 and j + l >= 18:
                        if i == k and j == l:
                            ans += a[i][j] * ( a[k][l] - 1 )
                        else:
                            ans += a[i][j] * a[k][l]
ans //= 2
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
for i in range(n):
  a.append(input())

findpoint = lambda s: 0 if (i := s.find('.')) == -1 else (len(s) - i - 1)
b = list(map(findpoint, a))
delpoint = lambda s: s.replace('.', '')
a = list(map(delpoint, a))

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = []
for i in range(n):
  a.append(input())

findpoint = lambda s: 0 if (i := s.find('.')) == -1 else (len(s) - i - 1)
b = list(map(findpoint, a))
delpoint = lambda s: s.replace('.', '')
a = list(map(delpoint, a))

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

Submission status: Runtime Error

Solution code:
N=int(input())
list1=[]
cnt=0
for i in range(N):
  list1.append(int(input()))
for i in range(N):
  for j in range(N-i-1):
    if isinstance(((list1[i])*(list1[j])),int):
      cnt=cnt+1
print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import itertools
from functools import reduce

def load():
    num = int(input())
    numbers = [float(input()) for _ in range(num)]

    return numbers


if __name__ == "__main__":
    numbers = load()
    counter = sum(filter(lambda _: _, map(lambda n: float.is_integer(n[0] * n[1]), itertools.combinations(numbers, 2)))
    print(counter)

Submission status: Runtime Error

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

def is_integer(number):
    # return float.is_integer(number)
    if float.is_integer(number):
        return 1
    return 0

def load():
    num = int(input())
    numbers = [float(input()) for _ in range(num)]

    return numbers


if __name__ == "__main__":
    numbers = load()
    counter = reduce(lambda a, b: a + is_integer(b[0] * b[1]), itertools.combinations(numbers, 2), 0)
    print(counter)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    cnt = [[0] * 18 for _ in range(41)]
    ans = 0
    for _ in range(N):
        a = input()
        if "." in a:
            b = int(a.replace(".", "") + "0" * (10 - (len(a) - a.index("."))))
        else:
            b = int(a) * 10 ** 9
        d2 = 0
        d5 = 0
        while b % 2 == 0:
            d2 += 1
            b //= 2
        while b % 5 == 0:
            d5 += 1
            b //= 5
        for i in range(max(0, 18-d2), 41):
            for j in range(max(0, 18-d5), 18):
                ans += cnt[i][j]
        cnt[d2][d5] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 36 - 1

a = [input()[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
  for i in range(l):
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)

Submission status: Runtime Error

Solution code:
def solve(a_list):
    cnt = 0
    a_list = [a * 1e9 for a in a_list]
    for a_1 in range(0, len(a_list) - 1):
        for a_2 in range(a_1 + 1, len(a_list)):
            if a_list[a_1] * a_list[a_2] % 1e18 == 0:
                cnt += 1
    print(cnt)


def get_input():
    N = int(input())
    ns = list()
    for i in range(N):
        ns.append(float(input()))


solve(a_list=get_input())

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import Counter
import sys

N = int(input())
K = 10**9
L = 10**18
A = [0] * N
C = Counter()
ans = 0

for i in range(N):
	A[i] = round(K * float(input()))
	C[gcd(A[i],L)] += 1 #辞書型だから[]内のkeyに対応するvalueの値を+1している。ここでは10^9-nの値をCに加えていっている。
	
for k1,v1 in C.items():
	for k2 ,v2 in C.items():
		if k1 == k2:
			if k1*k2 % L == 0:
				ans += v1*(v1-1)/2
		elif k1 < k2:
			if k1*k2 % L == 0:
				ans += v1 * v2

int(print(ans))

Submission status: Runtime Error

Solution code:
# A

n = int(input())
a_l = [int(float(input()) * 10**9) for x in range(n)]

list = [[0] * 18 for x in range(18)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]
    
ans = 0
for i in range(n):
    _t,_f = b_l[i]
    for j in range(18-_t,19):
        for k in range(18-_f,19):
            ans += list[j][k]
    if _t >= 9 and _f >= 9:
        ans -= 1
        
print(ans // 2)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

for i in range(n):
    s = input()
    x = s.find('.')
    if x == -1:
        s = s + '0'*9
    else:
        s = s.replace('.','') + '0'*(10-(len(s)-x))
    s = int(s)
    d2 = 0
    d5 = 0
    for i in range(20):
        if s%2 == 0:
            s = s//2
            d2 += 1
        else:
            break
    for i in range(20):
        if s%5 == 0:
            s = s//5
            d5 += 1
        else:
            break
    dp[d2][d5] += 1
    dq[d2][d5] += 1

for i in list(range(19))[::-1]:
    for j in list(range(19))[::-1]:
        dp[i][j-1]+=dp[i][j]
for j in list(range(19))[::-1]:
    for i in list(range(19))[::-1]:
        dp[i-1][j]+=dp[i][j]
ret = 0
for i in range(20):
    for j in range(20):
        ret += dq[i][j] * dp[18-i][18-j]
ret -= dp[9][9]
print(ret//2)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

for i in range(n):
    s = input()
    x = s.find('.')
    if x == -1:
        s = s + '0'*9
    else:
        s = s.replace('.','') + '0'*(10-(len(s)-x))
    s = int(s)
    d2 = 0
    d5 = 0
    for i in range(19):
        if s%2 == 0:
            s = s//2
            d2 += 1
        else:
            break
    for i in range(19):
        if s%5 == 0:
            s = s//5
            d5 += 1
        else:
            break
    dp[d2][d5] += 1
    dq[d2][d5] += 1

for i in range(17, - 1, -1):
    for j in range(17, - 1, -1):
        dp[i][j-1]+=dp[i][j]
for j in range(17, - 1, -1):
    for i in range(17, - 1, -1):
        dp[i-1][j]+=dp[i][j]
ret = 0
for i in range(19):
    for j in range(19):
        ret += dq[i][j] * dp[18-i][18-j]
ret -= dp[9][9]
print(ret//2)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
lst = []
for _ in range(n):
    a = input().split(".")
    if len(a) == 1:
        a[0] = a[0] + '0' * 9
        lst.append(int(a[0]))
    else:
        l = len(a[1])
        tmp = a[0] + a[1] + '0' * (9 - l)
        lst.append(int(tmp))


two = []
five = []
for i in lst:
    j = i
    cnt = 0
    while j % 2 == 0:
        j //= 2
        cnt += 1
    two.append(cnt)
    j = i
    cnt = 0
    while j % 5 == 0:
        j //= 5
        cnt += 1
    five.append(cnt)

a = [[0] * 25 for _ in range(25)]
for i, j in zip(two, five):
    a[i][j] += 1

S = [[0] * 25 for _ in range(25)]
for i in range(1, 25):
    for j in range(1, 25):
        S[i][j] = a[i-1][j-1] + S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]

ans = 0
for i, j in zip(two, five):
    if 18 - i < 0:
        i = 18
    if 18 - j < 0:
        j = 18
    ans += S[-1][-1] - S[-1][18 - j] - S[18 - i][-1] + S[18 - i][18 - j]
    if i + i >= 18 and j + j >= 18:
        ans -= 1
print(ans // 2)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
lst = []
for _ in range(n):
    a = input().split(".")
    if len(a) == 1:
        a[0] = a[0] + '0' * 9
        lst.append(int(a[0]))
    else:
        l = len(a[1])
        tmp = a[0] + a[1] + '0' * (9 - l)
        lst.append(int(tmp))


two = []
five = []
for i in lst:
    j = i
    cnt = 0
    while j % 2 == 0:
        j //= 2
        cnt += 1
    two.append(cnt)
    j = i
    cnt = 0
    while j % 5 == 0:
        j //= 5
        cnt += 1
    five.append(cnt)

a = [[0] * 25 for _ in range(25)]
for i, j in zip(two, five):
    a[i][j] += 1

S = [[0] * 25 for _ in range(25)]
for i in range(1, 25):
    for j in range(1, 25):
        S[i][j] = a[i-1][j-1] + S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]

ans = 0
for i, j in zip(two, five):
    ans += S[-1][-1] - S[-1][18 - j] - S[18 - i][-1] + S[18 - i][18 - j]
    if i + i >= 18 and j + j >= 18:
        ans -= 1
print(ans // 2)

Submission status: Runtime Error

Solution code:
MOD=10**9
from decimal import Decimal
import sys
input=sys.stdin.readline
    
def w(i,m):
    cnt=0
    while(i>0 and i%m==0):
        i//=m
        cnt+=1
    return cnt

N=int(input())
A=[int(Decimal(input())*Decimal(MOD)) for i in range(N)]
dic=[{} for i in range(N)]
dp=[[0]*51 for i in range(51)]

for i in range(N):
    dic[i][2],dic[i][5]=w(A[i],2),w(A[i],5)
    dp[dic[i][2]][dic[i][5]]+=1

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):
    t,f=max(18-dic[i][2],0),max(18-dic[i][5],0)
    res=dp[t][f]
    if t<=a and f<=b:
        res-=1
    ans+=res
print(ans//2)

Submission status: Runtime Error

Solution code:
n = int(input())
li = []
for _ in range(n):
  li.append(input())
  k = 1
res = 0
for i in li:
  for j in li[k:]:
    if (i*j).is_integer:
      res += 1
  k += 1
print(res)

Submission status: Runtime Error

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

B = [[0]*30 for i in range(30)]
ans1 = 0
for i in range(N):
    a = A[i]
    count1 = 0
    while a%2==0:
        a//=2
        count1+=1
    count2 = 0
    while a%5==0:
        a//=5
        count2+=1
    #print(count1,count2,A[i])
    B[count1][count2] += 1
    if count1>=9 and count2>=9:
        ans1+=1

C = [[0]*31 for i in range(31)]

for i in range(30):
    for j in range(30):
        C[i+1][j+1] = B[i][j] + C[i+1][j] + C[i][j+1] - C[i][j]

#print(*C,sep="\n")
ans = 0
for i in range(30):
    for j in range(30):
        k,l = min(18,i),min(18,j)
        #if B[i][j]>0:
        #    print(B[i][j],C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21],i,j)
        ans += B[i][j] * (C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21])

print((ans-ans1)//2)

Submission status: Runtime Error

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

B = [[0]*21 for i in range(21)]
ans1 = 0
for i in range(N):
    a = A[i]
    count1 = 0
    while a%2==0:
        a//=2
        count1+=1
    count2 = 0
    while a%5==0:
        a//=5
        count2+=1
    #print(count1,count2,A[i])
    B[count1][count2] += 1
    if count1>=9 and count2>=9:
        ans1+=1

C = [[0]*22 for i in range(22)]

for i in range(21):
    for j in range(21):
        C[i+1][j+1] = B[i][j] + C[i+1][j] + C[i][j+1] - C[i][j]

#print(*C,sep="\n")
ans = 0
for i in range(21):
    for j in range(21):
        k,l = min(18,i),min(18,j)
        #if B[i][j]>0:
        #    print(B[i][j],C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21],i,j)
        ans += B[i][j] * (C[21][21] + C[18-k][18-l] - C[21][18-l] - C[18-k][21])

print((ans-ans1)//2)

Submission status: Runtime Error

Solution code:
N=int(input())
D={}
from decimal import Decimal
A=[Decimal(input()) for _ in range(N)]
A=[int(i*10**9) for i in A]
for i in range(N):
  x=A[i]
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x=x//2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y=y//5
  A[fcnt][tcnt]+=1

cnt=0
for i in range(19):
  for j in range(19):
    for k in range(19):
      for l in range(19):
        if i+k>=18 and j+l>=18:
          if i!=k and j!=l:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          elif i==k and j==l:
            d=A[i][j]
            p=d*(d-1)
          else:
            d=A[i][j]
            e=A[k][l]
            p=d*e
          cnt+=p
print(cnt//2)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

root = 10000
MOD = 2 ** 61 - 1
def rolling_hash(s):
    hs = [0] * (len(s) + 1)
    for i in range(len(s)):
        hs[i + 1] = hs[i] * root + ord(s[i]) % MOD
    return hs

#"""
N = int(input())
S_list = [input() for _ in range(N)]
"""
def to_alpha(n):
    ret = ''
    while n > 0:
        n -= 1
        ret += chr(n % 26 + ord('a'))
        n //= 26
    return ret

N = 10 ** 5
S_list = [to_alpha(i) for i in range(2, 2 * N + 2, 2)]
#"""


S_list.sort(key=len)

ans = 0
wanted = {chr(i): set() for i in range(ord('a'), ord('z') + 1)}
for S in S_list:
    alpha_set = set()
    hash_of_S = rolling_hash(S)
    for i in range(len(S)):
        alpha_set.add(S[i])
        suffix_hash = (hash_of_S[len(S)] - hash_of_S[i+1] * pow(root, (len(S) - i - 1), MOD)) % MOD
        for alpha in alpha_set:
            if suffix_hash in wanted[alpha]:
                ans += 1

    suffix_of_S = (hash_of_S[len(S)] - hash_of_S[1] * pow(root, (len(S) - 1), MOD)) % MOD
    wanted[S[0]].add(suffix_of_S)

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [float(input()) for _ in range(n)]
a = [i*10**9 for i in a]
MAX = 25
p_mat = [[0 for _ in range(MAX)] for _ in range(MAX)]

for i in a:
    b_cnt = 0
    while i % 2 == 0:
        i /= 2
        b_cnt += 1
    f_cnt = 0
    while i % 5 == 0:
        i /= 5
        f_cnt += 1
    p_mat[b_cnt][f_cnt] += 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [float(input()) for _ in range(n)]
a = [i*10**9 for i in a]
MAX = 23
p_mat = [[0 for _ in range(MAX)] for _ in range(MAX)]

for i in a:
    b_cnt = 0
    while i % 2 == 0:
        i /= 2
        b_cnt += 1
    f_cnt = 0
    while i % 5 == 0:
        i /= 5
        f_cnt += 1
    p_mat[b_cnt][f_cnt] += 1

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