thanhchauns2's blog

Help me with this DP problem
By thanhchauns2, history, 4 years ago, In English

Given an array with N elements and a number P (P ≤ N). Pick randomly P elements from the array, let's call T the product of these elements. Find the largest x that T % 10^x = 0

Example:

Input

3 2

26 5 96

Output

1

Input

3 2

25 4 90

Output

2

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Sorry if i have some mistakes, i know english not well.

So. Main condition (T % 10^x == 0) Makes it clear that we need only 5 and 2 in decomposition of a number. We can write dp[i][j][k]. where i — how many 2 are in the decomposition of our K number, which we are choose and j — how many 5 in our decomposition. i, j are <= log5(maxA[i]) * n. And k <= n.

O(n^3 * log5(maxA[i])^2) I think it possible to solve better

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

https://codeforces.net/contest/837/problem/D

This is almost exactly the same problem but here you're restricted to choosing a subset of size k.

→ Reply