Problem:


Score : 300 points

Problem Statement

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

Constraints

2 \leq N \leq 200\,000

0 < A_i < 10^4

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

Input

Input is given from Standard Input in the following format.

N
A_1
A_2
\vdots
A_N

Output

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

Sample Input 1

5
7.5
2.4
17.000000001
17
16.000000000

Sample Output 1

3

There are 3 pairs with integer product:

7.5 \cdot 2.4 = 18

7.5 \cdot 16 = 120

17 \cdot 16 = 272

Sample Input 2

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

Sample Output 2

8



Sample input:
5
7.5
2.4
17.000000001
17
16.000000000


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import Fraction

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++




def main():
	n = int(input())
	#b , c = tin()
	al = [Fraction(input()) for _ in range(n)]
	ret = 0
	for i, vi in enumerate(al):
		for vj in al[i+1:]:
			if (vi*vj).denominator==1:
				ret += 1
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [float(input()) for _ in range(N)]
A.sort()
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if (A[i]*A[j]).is_integer() and A[i] != A[j]:
      ans += 1

  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ans=0
A=[0]*N
a=""
b=""
for i in range(N):
  s=input()
  if "." not in s:
    a=s
    b="000000000"
  else:
    a,b=s.split(".")
    b=b.ljust(9,"0")
  A[i]=int(a+b)
  for j in range(i):
    if i!=j:
      if A[i]*A[j]%(10**18)==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [int(float(input()) * 10**9) for _ in range(N)]

ans = 0
checker = 10 ** 18
for i, ai in enumerate(A):
    for j in range(i + 1, N):
        multi = ai * A[j]
        if multi % checker == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = []

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

count = 0

for i in range(n):
    for j in range(n):
        if i != j and i < j:
            temp = (a[i] * 10 ** 3) * (a[j] * 10 ** 3) / 10 ** 6
            #print(temp, int(temp))
            if temp - int(temp) == 0:
                count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, AS):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            if AS[i] * AS[j] % 1000000000_000000000 == 0:
                # debug(": AS[i], AS[j]", AS[i], AS[j])
                ret += 1
    return ret


def main():
    # parse input
    N = int(input())
    AS = []
    for i in range(N):
        s = input().strip()
        try:
            v = int(s) * 1000000000
        except:
            s1, s2 = s.split(b".")
            s2 = s2 + b"0" * (9 - len(s2))
            v = int(s1) * 1000000000 + int(s2)
        # print(v)
        AS.append(v)
    print(solve(N, AS))


# tests
T1 = """
5
7.5
2.4
17.000000001
17
16.000000000
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
8
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
n = int(readline())
a = []
for i in range(n):
    ai = readline().strip()
    idx = ai.find(".")
    if idx >= 0:
        v = len(ai)-idx-1
        ai = int(ai.replace(".",""))
    else:
        ai = int(ai)
        v = 0
    c2 = c5 = 0

    x = ai
    while x%2==0:
        c2 += 1
        x//=2
    
    x = ai
    while x%5==0:
        c5 += 1
        x//=5
    #print(ai,c2,c5)
    a.append((c2,c5,v))

ans = 0
for i in range(n):
    c,d,v = a[i]
    for j in range(i+1,n):
        e,f,w = a[j]
        if c+e >= v+w and d+f >= v+w:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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


            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [int(float(input()) * 10**9) for _ in range(N)]

ans = 0
for i, ai in enumerate(A):
    for j in range(i + 1, N):
        multi = ai * A[j]
        if multi % 10**18 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from decimal import Decimal
import sys
all_data = sys.stdin.read().split('\n')
n = int(all_data[0])
l = []
dp = defaultdict(int)
for _ in range(n):
  d = Decimal(all_data[_+1])
  d *= (10 ** 9)
  two = -9
  five = -9
  while d % 2 == 0:
    d //= 2
    two += 1
  while d % 5 == 0:
    d //= 5
    five += 1
  dp[(two, five)] += 1
ret = 0
for x in dp:
  for y in dp:
    if x == y:
      if x[0] >= 0 and x[1] >= 0:
        inc = dp[x]
        ret += inc * (inc-1)
    else: 
      if x[0] + y[0] >= 0 and x[1] + y[1] >= 0:
        ret += dp[x] * dp[y]
print(ret // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from decimal import Decimal
n = int(input())
l = []
dp = defaultdict(int)
for _ in range(n):
  d = Decimal(input())
  d *= (10 ** 9)
  two = -9
  five = -9
  while d % 2 == 0:
    d //= 2
    two += 1
  while d % 5 == 0:
    d //= 5
    five += 1
  dp[(two, five)] += 1
ret = 0
for x in dp:
  for y in dp:
    if x == y:
      if x[0] >= 0 and x[1] >= 0:
        inc = dp[x]
        ret += inc * (inc-1)
    else: 
      if x[0] + y[0] >= 0 and x[1] + y[1] >= 0:
        ret += dp[x] * dp[y]
print(ret // 2)

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
n = int(input())
a = [Decimal(input()) for i in range(n)]
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if (a[i]*a[j]) % 1 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
c = 0
from fractions import Fraction
for i in range(n):
    ai = Fraction(input())
    for x in a:
        if (x * ai).denominator == 1:
            c += 1
    a.append(ai)
print(c)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
D = dict()
TF = []
for _ in range(n):
  s = input()
  if "." not in s:
    s += "."
  a, b = s.split(".")
  k = len(b)
  c = int(a+b)
  t = 0
  while c%2 == 0:
    c //= 2
    t += 1
  f = 0
  while c%5 == 0:
    c //= 5
    f += 1
  t -= k
  f -= k
  TF.append((t, f))
D = Counter(TF)
ans = 0
for t1, f1 in D.keys():
  for t2, f2 in D.keys():
    if t1+t2 >= 0 and f1+f2 >= 0:
      ans += D[(t1, f1)] * D[(t2, f2)]
for t, f in TF:
  if t >= 0 and f >= 0:
    ans -= 1
ans //= 2
print(ans)

Submission status: Accepted

Solution code:
class BIT():
 
    __slots__ = ["n", "data"]
 
    def __init__(self, li):
        self.n = len(li) + 1
        self.data = [0] + li
        for i in range(1, self.n):
            if i + (i & -i) < self.n:
                self.data[i + (i & -i)] += self.data[i]
 
    def add(self, i, a):
        i += 1
        while i < self.n:
            self.data[i] += a
            i += i & -i
        
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def fold(self, l, r):
        res = 0
        while l < r:
            res += self.data[r]
            r -= r & -r
        while r < l:
            res -= self.data[l]
            l -= l & -l
        return res

import bisect
n = int(input())
TF = []
for _ in range(n):
  s = input()
  if "." not in s:
    s += "."
  a, b = s.split(".")
  k = len(b)
  c = int(a+b)
  t = 0
  while c%2 == 0:
    c //= 2
    t += 1
  f = 0
  while c%5 == 0:
    c //= 5
    f += 1
  TF.append((t-k, f-k))
TF.sort()
ans = 0
U = 50
bit = BIT([0]*100)
temp = n
for t, f in TF:
  r = bisect.bisect_left(TF, (-t, -U))
  while temp > r:
    temp -= 1
    nt, nf = TF[temp]
    bit.add(nf+U, 1)
  ans += n-temp - bit.acc(-f+U)
for t, f in TF:
  if min(t, f) >= 0:
    ans -= 1
ans //= 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
biga = []
for _ in range(n):
    a = float(input())
    a = round(a * 10 ** 9 + 0.1)
    biga.append(a)

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

arr = [[0 for _ in range(20)] for _ in range(20)]
p25 = []
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    p25.append([cnt2,cnt5])
    cnt2=min(19,cnt2)
    cnt5=min(19,cnt5)
    arr[cnt2][cnt5]+=1

ans=0
for i in range(20): # 2
    for j in range(20): # 5
        if arr[i][j]==0:
            continue
        for k in range(20): # 2
            for l in range(20): # 5
                if i+k>=18 and j+l>=18:
                    if i==k and j==l:
                        ans+= (arr[i][j]-1)*arr[k][l]
                    else:
                        ans+= arr[i][j]*arr[k][l]

print(ans//2)

Submission status: Accepted

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

arr = [[0 for _ in range(20)] for _ in range(20)]
p25 = []
for i in range(n):
    cnt2,cnt5=fact25(biga[i])
    p25.append([cnt2,cnt5])
    cnt2=min(19,cnt2)
    cnt5=min(19,cnt5)
    arr[cnt2][cnt5]+=1

ans=0
for i in range(20): # 2
    for j in range(20): # 5
        if arr[i][j]==0:
            continue
        for k in range(20): # 2
            for l in range(20): # 5
                if i+k>=18 and j+l>=18:
                    if i==k and j==l:
                        ans+= (arr[i][j]-1)*arr[k][l]
                    else:
                        ans+= arr[i][j]*arr[k][l]

print(ans//2)

Submission status: Accepted

Solution code:
def prog(x):
    n = len(x)

    def count25(s): # count25(0)
        if s.find('.') == -1:
            s += '.'
        s = s.rstrip('0')
        decimal_point = s.find('.')
        int_part = s[:decimal_point]
        float_part = s[decimal_point+1:]
        float_part += '0' * (9 - len(float_part))
        n = int(int_part + float_part)
        if n == 0:
            return (0, 0)
        two = five = 0
        while n % 2 == 0:
            two += 1
            n //= 2
        while n % 5 == 0:
            five += 1
            n //= 5
        return (two, five)

    d = {}
    for a in x:
        t = count25(a)
        d.setdefault(t, 0)
        d[t] += 1
    two_five = list(d.keys())
    count = 0
    for i in range(len(two_five)): # i = 0
        two, five = two_five[i]
        cnt = d[two_five[i]]
        if two >= 9 and five >= 9:
            count += cnt * (cnt -1) // 2
        for j in range(i + 1, len(two_five)):
            two2, five2 = two_five[j]
            if two + two2 >= 18 and five + five2 >= 18:
                count += cnt * d[two_five[j]]
    print(count)

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

Submission status: Accepted

Solution code:
def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


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

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

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

Submission status: Accepted

Solution code:
import math
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = []
    pair_count = Counter()
    for _ in range(N):
        line = input().strip()
        if '.' in line:
            a, b = line.split('.')
            d = 10**len(b)
            c = int(a)*d+int(b)
        else:
            c = int(line)
            d = 1
        gcd = math.gcd(c, d)
        c //= gcd
        d //= gcd
        pow2, pow5 = 0, 0
        while c and c%2 == 0:
            pow2 += 1
            c //= 2
        while c and c%5 == 0:
            pow5 += 1
            c //= 5
        while d and d%2 == 0:
            pow2 -= 1
            d //= 2
        while d and d%5 == 0:
            pow5 -= 1
            d //= 5
        pair_count[(pow2, pow5)] += 1
    answer = 0
    for pair0 in pair_count:
        for pair1 in pair_count:
            if pair0 < pair1 and pair0[0]+pair1[0] >= 0 and pair0[1]+pair1[1] >= 0:
                answer += pair_count[pair0]*pair_count[pair1]
            elif pair0 == pair1 and pair0[0] >= 0 and pair0[1] >= 0:
                answer += pair_count[pair0]*(pair_count[pair0]-1)//2
    return answer


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

Submission status: Accepted

Solution code:
import decimal

N = int(input())
A = [int(decimal.Decimal(input()) * 10 ** 9) for _ in range(N)]
B = [[0] * 19 for _ in range(19)]
for a in A:
    cnt2 = 0
    while a % 2 == 0:
        cnt2 += 1
        a //= 2
    cnt5 = 0
    while a % 5 == 0:
        cnt5 += 1
        a //= 5
    B[min(cnt2, 18)][min(cnt5, 18)] += 1
ans = 0
for i in range(361):
    a, r = divmod(i, 19)
    if a >= 9 and r >= 9:
        ans -= B[a][r]
    for j in range(361):
        b, s = divmod(j, 19)
        if a + b >= 18 and r + s >= 18:
            ans += B[a][r] * B[b][s]

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def getnigo(num):
    org = num
    if num in dic:
        return dic[num]
    ni, go = 0, 0
    while num % 2 == 0:
        ni += 1
        num //= 2
    while num % 5 == 0:
        go += 1
        num //= 5

    ni, go = min(18, ni), min(18, go)
    dic[org] = (ni, go)
    return ni, go

def solve(n=None, s1=None, s2=None):
    n = getN()
    li = []
    for i in range(n):
        s = getS()
        if "." not in s:
            num = int(s) *  10 ** 9
        else:
            sei, syo = s.split(".")
            num = int(sei) * 10 ** 9 + int(syo) * 10 ** (9 - len(syo))
        li.append(num)

    nigoli = [[0 for i in range(20)] for i in range(20)]

    for num in li:
        ni, go = getnigo(num)
        nigoli[ni][go] += 1

    for i in range(20):
        for j in range(18, -1, -1):
            nigoli[i][j] += nigoli[i][j+1]

    for i in range(18, -1, -1):
        for j in range(20):
            nigoli[i][j] += nigoli[i+1][j]

    # for lili in nigoli:
    #     print(lili)

    ans = 0
    for num in li:
        ni, go = getnigo(num)
        tni, tgo = 18 - ni, 18 - go
        ans += nigoli[tni][tgo]
        if ni >= 9 and go >= 9:
            ans -= 1
        # print(num, ni, go, ans)

    print(ans // 2)
    # print(getnigo(1))




def main():
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [input() for _ in [0]*n]
    b = []
    for i in a:
        j = i.find(".")
        if j == -1:
            b.append(int(i)*10**9)
        else:
            k = 10-len(i)+j
            i = i.replace(".", "")
            b.append(int(i)*10**k)
    d = dict()
    for i in b:
        cnt_a = 0
        while(True):
            if i % 2 != 0:
                break
            cnt_a += 1
            i //= 2
        cnt_b = 0
        while(True):
            if i % 5 != 0:
                break
            cnt_b += 1
            i //= 5
        if (cnt_a, cnt_b) in d:
            d[(cnt_a, cnt_b)] += 1
        else:
            d[(cnt_a, cnt_b)] = 1
    ans = 0
    for i in range(50):
        for j in range(20):
            if (i, j) not in d:
                continue
            temp1 = d[(i, j)]
            for k in range(50):
                for l in range(20):
                    if (k, l) not in d:
                        continue
                    temp2 = d[(k, l)]
                    if i+k >= 18 and j+l >= 18:
                        if i == k and j == l:
                            ans += temp1*(temp2-1)
                        else:
                            ans += temp1*temp2

    print(ans//2)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
import copy

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N = int(input())
    M = 101
    offset = M//2
    cnt = [[0]*M for _ in range(M)]
    p = [None for _ in range(N)]
    for i in range(N):
        A = input()
        n = len(A)
        tmp = [0,0]# 2と5の数を調べる。-は不足
        if '.' in A:
            tmp[0] -= n-1-A.index('.')
            tmp[1] -= n-1-A.index('.')
        A = int(A.replace('.',''))
        while A % 2 == 0:
            A //= 2
            tmp[0] += 1
        while A%5 == 0:
            A //= 5
            tmp[1] += 1
        cnt[offset+tmp[0]][offset+tmp[1]] += 1
        p[i] = (tmp[0]+offset, tmp[1]+offset)
    # print(cnt)
    cnt2 = copy.deepcopy(cnt)

    # 累積和をとる
    for i in range(M-1,-1,-1):
        for j in range(M-1,-1,-1):
            if j < M-1:
                cnt[i][j] += cnt[i][j+1]
    
    for i in range(M-1,-1,-1):
        for j in range(M-1,-1,-1):
            if i < M-1:
                cnt[i][j] += cnt[i+1][j]
    
    # print(cnt)
    ans = 0
    for i in range(M):
        for j in range(M):
            if cnt2[i][j]==0: continue
            ans += cnt2[i][j]*cnt[offset*2-i][offset*2-j]
            # print(p[i])
            # print(cnt[offset*2-p[i][0]][offset*2-p[i][1]])
            # ans += cnt[offset*2-p[i][0]][offset*2-p[i][1]]
            # print(i,j,cnt2[i][j],ans)
    print((ans-cnt[offset][offset])//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[input() for _ in range(n)]
m=30
c=[[0]*m for _ in range(m)]
k=9
ary=[]
for b in a:
  b=b.split('.')
  bint,bfl=0,0
  bint=int(b[0])*10**9
  if len(b)>1:
    tmp=('1'+b[1]+'000000000000')[:10]
    bfl=int(tmp)
    bfl-=10**9
  tmp=bint+bfl
  t=tmp
  n5=0
  while t%5==0:
    t//=5
    n5+=1
  t=tmp
  n2=0
  while t%2==0:
    t//=2
    n2+=1
  n2=min(n2,k+9)
  n5=min(n5,k+9)
  c[n2][n5]+=1
  ary.append([n2,n5])
cc=[[0]*(m+1) for _ in range(m+1)]
for i in range(m):
  for j in range(m):
    cc[i+1][j+1]+=cc[i+1][j]+c[i][j]
for i in range(m):
  for j in range(m):
    cc[i+1][j+1]+=cc[i][j+1]
ans=0

for i,j in ary:
  if i>=k and j>=k:ans-=1
  tmp=cc[-1][-1]-cc[-1][2*k-j]-cc[2*k-i][-1]+cc[2*k-i][2*k-j]
  ans+=tmp
ans//=2
print(ans)
"""
c[k][k]+=7
for x in c:
  print(x)
print('======')
for x in cc:
  print(x)
"""

Submission status: Accepted

Solution code:
import sys

import numpy as np
from numba import njit, i8


def input():
    return sys.stdin.readline().strip()


def convert(S):
    i, *d = S.split(".")
    i = int(i) * 1_000_000_000
    if d:
        return i + int(d[0].ljust(9, "0"))
    else:
        return i


def div_cnt(n, d):
    res = 0
    while n % d == 0:
        res += 1
        n //= d
    return res


@njit(i8(i8[:, :]), cache=True)
def solve(table):
    ans = 0
    for i in range(19):
        for j in range(19):
            cur = table[i][j]
            if cur == 0:
                continue
            for k in range(18 - i, 19):
                for l in range(18 - j, 19):
                    if k == i and j == l:
                        ans += cur * (cur - 1)
                    else:
                        ans += cur * table[k][l]
    return ans


N = int(input())
A = list(convert(input()) for _ in range(N))
divs = [(div_cnt(a, 2), div_cnt(a, 5)) for a in A]

table = np.zeros((19, 19), np.int64)
for t, f in divs:
    table[min(t, 18)][min(f, 18)] += 1
print(solve(table) // 2)

Submission status: Accepted

Solution code:
N = int(input())
dic = {}
for i in range(N):
  temp = str(input())
  temp = list(temp); N = len(temp)
  A = 0; dec = 0
  for j in range(N):
    if temp[j] != ".":
      A += int(temp[j])*pow(10,N-1-j)
    else:
      dec = N-1-j
      A //= 10
  t = -dec; f = -dec
  while A%2 == 0:
    t +=1 
    A = A//2
  while A%5 == 0:
    f += 1
    A = A//5
  #print(t,f)
  if (t,f) not in dic:
    dic[(t,f)] = 1
  else:
    dic[(t,f)] += 1
#print(dic)
V = list(dic.keys())
#print(V)
ans = 0
for i in range(len(V)):
  if V[i][0] >= 0 and V[i][1] >= 0:
    kosu = dic[V[i]]
    ans += kosu*(kosu-1)//2
for i in range(len(V)):
  for j in range(i+1,len(V)):
    keyi = V[i]
    keyj = V[j]
    if V[i][0]+V[j][0] >= 0 and V[i][1]+V[j][1] >= 0:
      ans += dic[keyi]*dic[keyj]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
T = [[0]*19 for _ in [0]*19]


def count25(x):
    c2 = c5 = 0
    while x % 2 == 0:
        x //= 2
        c2 += 1
    while x % 5 == 0:
        x //= 5
        c5 += 1
    return c2, c5


for _ in range(N):
    a, *b = input().split('.')
    x = int(a) * 10**9
    if b:
        x += int(b[0])*10**(10-len(b[0]))
    c2, c5 = count25(x)
    T[min(18, c2)][min(18, c5)] += 1

ans = 0
for c2 in range(19):
    for c5 in range(19):
        tt = T[c2][c5]
        if tt == 0:
            continue

        for i in range(18-c2, 19):
            for j in range(18-c5, 19):
                if c2 == i and c5 == j:
                    ans += tt*(tt-1)
                else:
                    ans += tt * T[i][j]

print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
al = []
for _ in range(n):
    s = input()
    if not '.' in s:
        al.append(int(s)*(10**9))
    else:
        syosu_keta = len(s.split('.')[1])
        rem = 9 - syosu_keta
        a = int(s.replace('.',''))
        a *= (10**rem)
        al.append(a)


al25 = [ [0]*19 for _ in range(19) ]
ans = 0
for a in al:
    cnt2 = 0
    cnt5 = 0
    curr_a = a
    for i in range(18):
        if curr_a%2 == 0:
            cnt2 += 1
            curr_a = curr_a//2
        else:
            break
    curr_a = a
    for i in range(18):
        if curr_a%5 == 0:
            cnt5 += 1
            curr_a = curr_a//5
        else:
            break

    for i in range(18-cnt2,19):
        for j in range(18-cnt5,19):
            ans += al25[i][j]

    al25[cnt2][cnt5] += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9+7

N = int(input())
A = [Fraction(input())*10**9 for _ in range(N)]

d = defaultdict(int)

for i in range(N):
    n = A[i]
    c2 = 0
    while n%2 == 0:
        n //= 2
        c2 += 1

    n = A[i]
    c5 = 0
    while n%5 == 0:
        n //= 5
        c5 += 1

    c2 = min(c2,18)
    c5 = min(c5,18)

    d[(c2,c5)] += 1

ans = 0
for k2,k5 in d.keys():
    for l2,l5 in d.keys():
        if k2 + l2 >= 18 and k5 + l5 >= 18:
            if k2 == l2 and k5 == l5:
                ans += d[(k2,k5)]*(d[(k2,k5)]-1)
            else:
                ans += d[(k2,k5)]*d[(l2,l5)]

print(ans//2)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    # 2と5を因数としていくつ含むか
    cnt = collections.Counter()
    for _ in range(N):
        A = SS()
        cnt2 = 0
        cnt5 = 0
        if '.' in A:
            idx = A.index('.')
            cnt2 -= len(A) - 1 - idx
            cnt5 -= len(A) - 1 - idx
            A = int(A[:idx] + A[idx+1:])
        else:
            A = int(A)
        while A % 2 == 0:
            A //= 2
            cnt2 += 1
        while A % 5 == 0:
            A //= 5
            cnt5 += 1
        cnt[(cnt2, cnt5)] += 1

    ans = 0
    for c0, c1 in itertools.combinations_with_replacement(cnt.items(), 2):
        k0, v0 = c0
        k1, v1 = c1
        if k0[0] + k1[0] >= 0 and k0[1] + k1[1] >= 0:
            if k0 == k1:
                ans += v0 * (v0 - 1) // 2
            else:
                ans += v0 * v1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
d={}
res=[[0,0] for _ in range(n)]
for i in range(n):
    a=float(input())
    b=round(a*pow(10,9))
    x=0
    y=0
    f=True
    while f:
        f=False
        if b%2==0:
            x+=1
            b=b//2
            f=True
        if b%5==0:
            y+=1
            b=b//5
            f=True
    if x*100+y not in d:
        d[x*100+y]=1
    else:
        d[x*100+y]+=1
    res[i]=[x,y]
ans=0
for i in range(n):
    x,y=res[i]
    for j in d:
        xc=j//100
        yc=j%100
        if xc+x>=18 and yc+y>=18:
            if xc==x and yc==y:
              ans+=d[j]-1
            else:
              ans+=d[j]
print(ans//2)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
d={}
res=[[0,0] for _ in range(n)]
for i in range(n):
    a=float(input())
    b=int(round(a*pow(10,9)))
    x=0
    y=0
    f=True
    while f:
        f=False
        if b%2==0:
            x+=1
            b=b//2
            f=True
        if b%5==0:
            y+=1
            b=b//5
            f=True
    if x*100+y not in d:
        d[x*100+y]=1
    else:
        d[x*100+y]+=1
    res[i]=[x,y]
ans=0
for i in range(n):
    x,y=res[i]
    for j in d:
        xc=j//100
        yc=j%100
        if xc+x>=18 and yc+y>=18:
            if xc==x and yc==y:
              ans+=d[j]-1
            else:
              ans+=d[j]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = [int(round(float(input()) * 10 ** 9)) for _ in range(N)]

# 2と5で割れる回数を考える
# 両方9回以上あれば整数(10^9分もどしても)OK
# これをDPする
def factor_2_5(n):
    two, five = 0, 0
    while n % 2 == 0:
        two += 1
        n //= 2
    while n % 5 == 0:
        five += 1
        n //= 5
    return two, five

res = defaultdict(int)
two_flag, five_flag = False, False
for ai in A:
    two, five = factor_2_5(ai)
    if two >= 9:
        two_flag = True
    if five >= 9:
        five_flag = True

    res[(two, five)] += 1

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

print(ans // 2)