Số zero tận cùng

lqdoj
 avatar
tocdovodoi
plain_text
2 months ago
789 B
7
Indexable
Never
MAX5 = 1000
def maximumZeros(arr, n, k):
    global MAX5
    subset = [[-1] * (MAX5 + 5) for _ in range(k + 1)]
    subset[0][0] = 0
    for p in arr:
        pw2, pw5 = 0, 0
        while not p % 2 :
            pw2 += 1
            p //= 2
        while not p % 5 :
            pw5 += 1
            p //= 5
        for i in range(k-1, -1, -1):
            for j in range(MAX5):
                if subset[i][j] != -1:
                    subset[i + 1][j + pw5] = (
                        max(subset[i + 1][j + pw5],
                        (subset[i][j] + pw2)))
    ans = 0
    for i in range(MAX5):
        ans = max(ans, min(i, subset[k][i]))
    return ans
n,k = map(int,input().split())
arr = [int(x) for x in input().split()]
print(maximumZeros(arr, n, k))
Leave a Comment