Блог пользователя thanhchauns2

Help me with this DP problem
Автор thanhchauns2, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

https://mirror.codeforces.com/contest/837/problem/D

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

→ Ответить