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: Wrong Answer

Solution code:
def howmany2_5(x):
    x = x * 10 ** 9
    n2, n5 = 0, 0
    while x % 2 == 0:
        n2 += 1
        x //= 2
    while x % 5 == 0:
        n5 += 1
        x //= 5
    
    if n2 > 18:
        n2 = 18
    if n5 > 18:
        n5 = 18
    
    return (n2, n5)

def lower_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] >= x:
            t = m
        else:
            s = m
    
    return t
    

def upper_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] > x:
            t = m
        else:
            s = m
    
    return t
    
def lower_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] >= x:
            t = m
        else:
            s = m
            
    return t

def upper_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] > x:
            t = m
        else:
            s = m
            
    return t


N = int(input())
A = [howmany2_5(float(input())) for _ in range(N)]
A.sort()
B = []
for i in range(19):
    B.append(list(map(lambda x: x[1], A[lower_bound_0(A, i): upper_bound_0(A, i)])))
C = []
for i in range(19):
    C.append([upper_bound_1(B[i], j) - lower_bound_1(B[i], j) for j in range(19)])
    
ans = 0
for i in range(9):
    for j in range(19):
        cnt = C[i][j]
        for k in range(18 - i, 19):
            ans += sum(C[k][18-i:]) * cnt


for i in range(9, 19):
    for j in range(9):
        cnt = C[i][j]
        for k in range(9, 19):
            ans += sum(C[k][18-i:]) * cnt

upper_9_9 = 0
for i in range(9, 19):
    upper_9_9 += sum(C[i][9:])
ans += upper_9_9 * (upper_9_9 - 1) // 2

print(ans)

Submission status: Wrong Answer

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

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

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

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

print(Ans)

Submission status: Wrong Answer

Solution code:
a = int(input())
b = [float(input()) for i in range(a)]

l = []
for i in range(a):
    for j in range(1,a):
        if i<j:
            l.append(b[i]*b[j])
f = 0
for i in range(len(l)):
    if l[i].is_integer() == True:
        f += 1

print(f)

Submission status: Wrong Answer

Solution code:
a = int(input())
b = [float(input()) for i in range(a)]

l = []
for i in range(a):
    for j in range(1,a):
        if i<j:
            l.append(b[i]*b[j])
f = 0
for i in range(len(l)):
    if l[i].is_integer() == True:
        f += 1

print(f)

Submission status: Wrong Answer

Solution code:
a = int(input())
b = [float(input()) for i in range(a)]

l = []
for i in range(a):
    for j in range(1,a):
        l.append(b[i]*b[j])
f = 0
for i in range(len(l)):
    if l[i].is_integer() == True:
        f += 1

print(int(f)/2)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[float(input()) for i in range(n)]
cou=0
for i in range(n):
  for j in range(i+1,n):
      # if a[i]==int(a[i]) and a[j]==int(a[j]):
        
      #   cou+=1
      # elif a[i]==int(a[i]):
      #   aj=a[j]-int(a[j])
      #   b=aj*a[i]
      #   c=b-int(b)
      #   if c==0:
      #     cou+=1
      # elif a[j]==int(a[j]):
      #   ai=a[i]-int(a[i])
      #   b=ai*a[j]
      #   c=b-int(b)
      #   if c==0:
      #     cou+=1  

      # else:

        b=a[i]*a[j]
        # c=b-int(b)
        if b.is_integer():
          
          cou+=1
print(cou)

Submission status: Wrong Answer

Solution code:
#from sys import stdin
#input = stdin.buffer.readline

n = int(input())
ans = 0
c = []
for i in range(n):
	x = int(float(input()) * 10 ** 9)
	#print(x)
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	c.append((a, b))
c.sort()
#print(c)
s = [0] * 20
j = n - 1
for i in range(n):
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	#print(s)
	for k in range(18 - c[i][1], 20):
		ans += s[k]
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
print(ans // 2)

Submission status: Wrong Answer

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

n = int(input())
ans = 0
c = []
for i in range(n):
	x = int(float(input()) * 10 ** 9)
	#print(x)
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	assert b < 19
	c.append((a, b))
c.sort()
#print(c)
s = [0] * 20
i, j = 0, n - 1
while i < n:
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	#print(s)
	for k in range(18 - c[i][1], 20):
		ans += s[k]
	i += 1
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
print(ans // 2)

Submission status: Wrong Answer

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

n = int(input())
ans = 0
c = []
for i in range(n):
	x = int(float(input()) * 10 ** 9)
	#print(x)
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	c.append((a, b))
c.sort()
#print(c)
s = [0] * 20
i, j = 0, n - 1
while i < n:
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	#print(s)
	for k in range(max(0, 18 - c[i][1]), 20):
		ans += s[k]
	i += 1
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
print(ans // 2)

Submission status: Wrong Answer

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

n = int(input())
ans = 0
c = []
for i in range(n):
	x = int(float(input()) * 10 ** 9)
	#print(x)
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	c.append((a, b))
c.sort()
#print(c)
s = [0] * 20
i, j = 0, n - 1
while i < n:
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	#print(s)
	for k in range(18 - c[i][1], 20):
		ans += s[k]
	i += 1
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
assert ans & 1 == 0
print(ans // 2)

Submission status: Wrong Answer

Solution code:
# A

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

list = [[0] * 19 for _ in range(19)]
cs_list = [[0] * 19 for _ in range(19)]
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]

for i in range(19):
    for j in range(19):
        for k in range(i+1):
            for l in range(j+1):
                cs_list[k][l] += list[i][j]

ans = 0
for i in range(n):
    _t,_f = b_l[i]
    if _t >= 9 and _f >= 9:
        ans -= 1
    ans += cs_list[18-_t][18-_f]
        
print(ans // 2)

Submission status: Wrong Answer

Solution code:
# A

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

list = [[0] * 19 for _ in range(19)]
cs_list = [[0] * 19 for _ in range(19)]
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]

for i in range(19):
    for j in range(19):
        for k in range(i+1):
            for l in range(j+1):
                cs_list[k][l] += list[i][j]

ans = 0
for i in range(n):
    _t,_f = b_l[i]
    if _t >= 9 and _f >= 9:
        ans -= 1
    ans += cs_list[18-_t][18-_f]
        
print(ans // 2)

Submission status: Wrong Answer

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

n = int(input())
ans = 0
c = []
for i in range(n):
	x = int(float(input()) * 10 ** 9)
	a = b = 0
	while not x & 1:
		a += 1
		x >>= 1
	while not x % 5:
		b += 1
		x //= 5
	c.append((a, b))
c.sort()
#print(c)
s = [0] * 20
i, j = 0, n - 1
while i < n:
	while j >= 0 and c[j][0] >= 18 - c[i][0]:
		s[c[j][1]] += 1
		j -= 1
	#print(s)
	for k in range(18 - c[i][1], 20):
		ans += s[k]
	i += 1
for i in c:
	if 2 * min(i) >= 18:
		ans -= 1
print(ans // 2)

Submission status: Wrong Answer

Solution code:
# A

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

list = [[0] * 19 for x in range(19)]
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: Wrong Answer

Solution code:
# A

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

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

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

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 19:
        _t5 += 1
        _a /= 5
    
    list[min(_t2,18)][min(_t5,18)] += 1
    b_l[i] = [min(_t2,18), min(_t5,18)]
    
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: Wrong Answer

Solution code:
# A

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

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

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

    _a = a_l[i]
    while _a % 5 == 0 or _t5 < 19:
        _t5 += 1
        _a /= 5
    
    list[min(_t2,18)][min(_t5,18)] += 1
    b_l[i] = [min(_t2,18), min(_t5,18)]
    
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: Wrong Answer

Solution code:
# A

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

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

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

    _a = a_l[i]
    while _a % 5 == 0:
        _t5 += 1
        _a /= 5
    
    list[min(_t2,18)][min(_t5,18)] += 1
    b_l[i] = [min(_t2,18), min(_t5,18)]
    
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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
MAX = 50


def resolve():
    n = int(input())

    D = [[0] * MAX for _ in range(MAX)]
    for _ in range(n):
        a = int(round(float(input()) * 10 ** 9))
        t = a
        x = 0
        while t % 2 == 0:
            t //= 2
            x += 1
        t = a
        y = 0
        while t % 5 == 0:
            t //= 5
            y += 1
        D[x][y] += 1

    res = 0
    for x1 in range(MAX):
        for y1 in range(MAX):
            for x2 in range(MAX):
                for y2 in range(MAX):
                    if x1 + x2 >= 18 and y1 + y2 >= 18:
                        if x1 + y1 < x2 + y2:
                            res += D[x1][y1] * D[x2][y2]
                        elif x1 == x2 and y1 == y2:
                            res += D[x1][y1] * (D[x1][y1] - 1) // 2
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

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

K = 10**9
L = K**2
D = defaultdict(int)
for _ in range(int(input())):
    D[gcd(int(float(input()) * K), L)] += 1

D = tuple(D.items())
ans = 0
for i, (k1, v1) in enumerate(D):
    if k1*k1 % L == 0:
        ans += v1*(v1-1) // 2
    for k2, v2 in D[i+1:]:
        if k1*k2 % L == 0:
            ans += v1 * v2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

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

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,vF):
	P,E = 1e9, 1e-3
	vA = [int(f*P+E) for f in vF]
	
	def divcnt(n):
		m,n = n,n
		a,b = 0,0
		while m%2<1: m//=2; a+=1
		while n%5<1: n//=5; b+=1
		return a,b

	vM = [divcnt(a) for a in vA]
	
	mX = [[0,]*50 for _ in "*"*50]
	for a,b in vM:
		mX[a][b] += 1
	
	mC = [[0,]*51,]
	for vX in mX:
		vC = [0,]
		t = 0
		for c,x in zip(mC[-1][1:],vX):
			t += x
			vC.append(t+c)
		mC.append(vC)
	
	res = 0
	
	for a,b in vM:
		y = max(18-a, 0)
		x = max(18-b, 0)
		t = N - mC[x][-1] - mC[-1][y] + mC[x][y]
		if x<=b and y<=a:
			t-=1
		#t//=2
		#print(t,a,b)##
		res += t

	print(res//2)


def main():
	N, = linput()
	sol(N, vinput(N,float))

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def howmany2_5(x):
    x = x * 10 ** 9
    n2, n5 = 0, 0
    while x % 2 == 0:
        n2 += 1
        x //= 2
    while x % 5 == 0:
        n5 += 1
        x //= 5
    
    if n2 > 18:
        n2 = 18
    if n5 > 18:
        n5 = 18
    
    return (n2, n5)

def lower_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] >= x:
            t = m
        else:
            s = m
    
    return t
    

def upper_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] > x:
            t = m
        else:
            s = m
    
    return t
    
def lower_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] >= x:
            t = m
        else:
            s = m
            
    return t

def upper_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] > x:
            t = m
        else:
            s = m
            
    return t


N = int(input())
A = [howmany2_5(float(input())) for _ in range(N)]
A.sort()
B = [] # B[i][j], i は約数に2が幾つ含まれているか、 B[i][j] は約数に5が幾つ含まれているかを表す。
for i in range(19):
    B.append(list(map(lambda x: x[1], A[lower_bound_0(A, i): upper_bound_0(A, i)])))


ans = 0
for i in range(9):
    for j in range(19):
        cnt = upper_bound_1(B[i], j) - lower_bound_1(B[i], j)
        for k in range(18 - i, 19):
            ans += (len(B[k]) - lower_bound_1(B[k], 18-j)) * cnt


for i in range(9, 19):
    for j in range(9):
        cnt = upper_bound_1(B[i], j) - lower_bound_1(B[i], j)
        for k in range(9, 19):
            ans += (len(B[k]) - lower_bound_1(B[k], 18-j)) * cnt

upper_9_9 = 0
for i in range(9, 19):
    upper_9_9 += len(B[i]) - lower_bound_1(B[i], 9)
ans += upper_9_9 * (upper_9_9 - 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
def howmany2_5(x):
    x = x * 10 ** 9
    n2, n5 = 0, 0
    while x % 2 == 0:
        n2 += 1
        x //= 2
    while x % 5 == 0:
        n5 += 1
        x //= 5
    
    if n2 >= 18:
        n2 = 18
    if n5 >= 18:
        n5 = 18
    
    return (n2, n5)

def lower_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] >= x:
            t = m
        else:
            s = m
    
    return t
    

def upper_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] > x:
            t = m
        else:
            s = m
    
    return t
    
def lower_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] >= x:
            t = m
        else:
            s = m
            
    return t

def upper_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] > x:
            t = m
        else:
            s = m
            
    return t


N = int(input())
A = [howmany2_5(float(input())) for _ in range(N)]
A.sort()
B = [] # B[i][j], i は約数に2が幾つ含まれているか、 B[i][j] は約数に5が幾つ含まれているかを表す。
for i in range(19):
    B.append(list(map(lambda x: x[1], A[lower_bound_0(A, i): upper_bound_0(A, i)])))


ans = 0
for i in range(9):
    for j in range(19):
        cnt = upper_bound_1(B[i], j) - lower_bound_1(B[i], j)
        for k in range(18 - i, 19):
            ans += (len(B[k]) - lower_bound_1(B[k], 18-j)) * cnt


for i in range(9, 19):
    for j in range(8):
        cnt = upper_bound_1(B[i], j) - lower_bound_1(B[i], j)
        for k in range(9, 19):
            ans += (len(B[k]) - lower_bound_1(B[k], 18-j)) * cnt

upper_9_9 = 0
for i in range(9, 19):
    upper_9_9 += len(B[i]) - lower_bound_1(B[i], 9)
ans += upper_9_9 * (upper_9_9 - 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
def howmany2_5(x):
    x = x * 10 ** 9
    n2, n5 = 0, 0
    while x % 2 == 0:
        n2 += 1
        x //= 2
    while x % 5 == 0:
        n5 += 1
        x //= 5
    
    return (n2, n5)

def lower_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] >= x:
            t = m
        else:
            s = m
    
    return t
    

def upper_bound_0(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m][0] > x:
            t = m
        else:
            s = m
    
    return t
    
def lower_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] >= x:
            t = m
        else:
            s = m
            
    return t

def upper_bound_1(A, x):
    s, t = -1, len(A)
    while t - s > 1:
        m = (s + t) // 2
        if A[m] > x:
            t = m
        else:
            s = m
            
    return t


N = int(input())
A = [howmany2_5(float(input())) for _ in range(N)]
A.sort()
B = [] # B[i][j], i は約数に2が幾つ含まれているか、 B[i][j] は約数に5が幾つ含まれているかを表す。
for i in range(18):
    B.append(list(map(lambda x: x[1], A[lower_bound_0(A, i): upper_bound_0(A, i)])))
B.append(sorted(list(map(lambda x: x[1], A[lower_bound_0(A, 18): N]))))


ans = 0
for i in range(9):
    for b in B[i]:
        for k in range(18 - i, 19):
            ans += len(B[k]) - lower_bound_1(B[k], 18 - b)


for i in range(lower_bound_1(B[9], 9)):
    for j in range(9, 19):
        ans += len(B[j]) - lower_bound_1(B[j], 18 - B[9][i])

b9_9 = upper_bound_1(B[9], 9) - lower_bound_1(B[9], 9)
ans += b9_9 * (b9_9 - 1) // 2
ans += b9_9 * (len(B[9]) - lower_bound_1(B[9], 10))

for b in B[9][lower_bound_1(B[9], 9):]:
    for j in range(10, 19):
        ans += len(B[j]) - lower_bound_1(B[j], 18 - b)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def dev(a):
    d = {}
    for i in (2, 5):
        r = 0
        while a % i == 0:
            r += 1
            a //= i
        d[i] = r
    return d


def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = float(input()) * (10 ** 9)
        A.append(dev(a))
    
    S2 = [set() for _ in range(19)]
    S5 = [set() for _ in range(19)]

    for i, a in enumerate(A):
        S2[min(a[2], 18)].add(i)
        S5[min(a[5], 18)].add(i)
    
    for i in range(18, 0, -1):
        S2[i - 1] |= S2[i]
        S5[i - 1] |= S5[i]

    res = 0
    for i, a in enumerate(A):
        s2 = S2[18 - min(18, a[2])]
        s5 = S5[18 - min(18, a[5])]
        s = (s2 & s5) | {i}
        res += len(s) - 1

    print(res // 2)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from decimal import Decimal

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
num=[[0]*23 for _ in range(40)]
for i in range(n):
	s=input()
	two=0;five=0
	if "." not in s:
		s=int(s)
		while s%2==0:
			s//=2
			two+=1
		while s%5==0:
			s//=5
			five+=1
	else:
		a,b=s.split(".")
		l=len(b)
		s=int(a)*10**l+int(b)
		five=-l;two=-l
		while s%2==0:
			s//=2
			two+=1
		while s%5==0:
			s//=5
			five+=1	
	num[two+9][five+9]+=1
ans=0
for i in range(40):
	for j in range(23):
		for k in range(i,40):
			for l in range(j,23):
				if i+k>=18 and j+l>=18:
					if (i,j)==(k,l):
						ans+=num[i][j]*(num[i][j]-1)//2
					else:
						ans+=num[i][j]*num[k][l]
print(ans)

Submission status: Wrong Answer

Solution code:
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

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

print(ans)

Submission status: Wrong Answer

Solution code:
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

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

print(ans)

Submission status: Wrong Answer

Solution code:
def decomp(m):
    p2=0
    p5=0
    while m%2==0:
        m//=2
        p2+=1
    while m%5==0:
        m//=5
        p5+=1
    return p2,p5

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

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[float(input()) for i in range(N)]
COUNT=0
for i in range(N):
    for a in range(i+1,N):
        x=A[i]*A[a]
        y=x%1
        if y==0:
            COUNT+=1

print(COUNT)

Submission status: Wrong Answer

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 (float(i)*float(j)).is_integer():
            res += 1
    k += 1
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
D={}
for i in range(N):
  a=float(input())
  a*=10**9
  x=int(a)
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x//=2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y//=5
  if (tcnt,fcnt) not in D:
    D[((tcnt,fcnt))]=1
  else:
    D[((tcnt,fcnt))]+=1

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

Submission status: Wrong Answer

Solution code:
N=int(input())
D={}
for i in range(N):
  a=float(input())
  a*=10**9
  x=int(a)
  y=x
  tcnt,fcnt=0,0
  while x%2==0 and tcnt<18:
    tcnt+=1
    x//=2
  while y%5==0 and fcnt<18:
    fcnt+=1
    y//=5
  if (tcnt,fcnt) not in D:
    D[((tcnt,fcnt))]=1
  else:
    D[((tcnt,fcnt))]+=1

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

Submission status: Wrong Answer

Solution code:
import collections

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

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

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

Submission status: Wrong Answer

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

for i in a:
    b_cnt = 0
    while i % 2 == 0 and b_cnt < 18:
        i //= 2
        b_cnt += 1
    f_cnt = 0
    while i % 5 == 0 and f_cnt < 18:
        i //= 5
        f_cnt += 1
    p_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)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce


# 画像でおいた自分の解説見て
N = a_int()
B = []
for _ in ra(N):
    A = read()[:-1]  # floatで扱うと誤差で死ぬ
    if '.' not in A:
        A += '.'
    for _ in range(9 - A[::-1].index('.')):
        A += '0'
    B.append(int(A[:-10] + A[-9:]))

N = []
M = []
for b in B:
    n = 0
    while ~b & 1:  # 偶数である限り
        b >>= 1
        n += 1
    N.append(n)

    m = 0
    while b % 5 == 0:  # 5で割れる限り
        b //= 5
        m += 1
    M.append(m)

cnt = [[0] * 19 for _ in ra(19)]
ans = 0
for n, m in zip(N, M):
    x = 18 - n
    y = 18 - m
    for i, j in product(range(x, 19), range(y, 19)):
        ans += cnt[i][j]

    # このデータをcntに追加
    cnt[min(n, 18)][min(m, 18)] += 1

print(ans)