乘积凑整(Product Rounding)

题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，请从中挑出 $k$ 个数，将它们乘起来，使它们的积在十进制表示下，末尾的零尽量多。

输入格式

• 第一行：两个整数 $n$ 和 $k$；
• 第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

• 单个整数：表示积的末尾最多有多少个 0。

样例输入 #1

3 2
4 20 50

样例输出 #1

3

样例说明 #1

$50\times 20=1000$。

样例输入 #2

5 3
15 16 3 25 9

样例输出 #2

3

样例说明 #2

$15\times 25\times 16=6000$。

数据范围

• 对于 50% 的数据，$1\leq k\leq n\leq 20$；
• 对于 100% 的数据，$1\leq k\leq n\leq 200$；
• $1\leq a_i\leq 10^{18}$。

知识点与难度

本题涉及的知识点从属于 GESP 6级（变形背包动态规划），难度等级：⭐⭐⭐。

测试点分布