Problem: 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.

Submission attempts (in order):
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)

def howmany2_5(x):
    x = round(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-j:]) * 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-j:]) * 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)

Verdicts: Wrong Answer

Accepted