304377: CF837D. Round Subset

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Round Subset

题意翻译

## 题目描述 我们把一个数的 roundness 值定义为它末尾 $0$ 的个数。 给你一个长度为 $n$ 的数列,要求你从中选出 $k$ 个数,使得这些选出的数的积的 roundness 值最大。 ## 输入格式 第一行包括两个正整数 $n$ 和 $k$($1 \leq n \leq 200$,$1 \leq k \leq n$)。 第二行包括 $n$ 个空白分隔的数 $a_1,a_2,\ldots,a_n$($1 \leq a_i \leq 10^{18}$)。 ## 输出格式 输出一个整数,是选择 $k$ 个数并作积的最大 roundness 值。 ## 样例解释 在第一个例子中,有三种选法。$[50,4]$ 的积是 $200$,roundness 值是 $2$;$[4,20]$ 的积是 $80$,roundness 值是 $1$;$[50,20]$ 的积是 $1000$,roundness 值是 $3$。 第二个例子中选法 $[15,16,25]$ 的积是 $6000$,roundness 值是 $3$。 第三个例子中所有的选法的积的 roundness 值都是 $0$。 translated by @poorpool

题目描述

Let's call the roundness of the number the number of zeros to which it ends. You have an array of $ n $ numbers. You need to choose a subset of exactly $ k $ numbers so that the roundness of the product of the selected numbers will be maximum possible.

输入输出格式

输入格式


The first line contains two integer numbers $ n $ and $ k $ ( $ 1<=n<=200,1<=k<=n $ ). The second line contains $ n $ space-separated integer numbers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{18} $ ).

输出格式


Print maximal roundness of product of the chosen subset of length $ k $ .

输入输出样例

输入样例 #1

3 2
50 4 20

输出样例 #1

3

输入样例 #2

5 3
15 16 3 25 9

输出样例 #2

3

输入样例 #3

3 3
9 77 13

输出样例 #3

0

说明

In the first example there are 3 subsets of 2 numbers. $ [50,4] $ has product 200 with roundness 2, $ [4,20] $ — product 80, roundness 1, $ [50,20] $ — product 1000, roundness 3. In the second example subset $ [15,16,25] $ has product 6000, roundness 3. In the third example all subsets has product with roundness 0.

Input

题意翻译

## 题目描述 我们把一个数的 roundness 值定义为它末尾 $0$ 的个数。 给你一个长度为 $n$ 的数列,要求你从中选出 $k$ 个数,使得这些选出的数的积的 roundness 值最大。 ## 输入格式 第一行包括两个正整数 $n$ 和 $k$($1 \leq n \leq 200$,$1 \leq k \leq n$)。 第二行包括 $n$ 个空白分隔的数 $a_1,a_2,\ldots,a_n$($1 \leq a_i \leq 10^{18}$)。 ## 输出格式 输出一个整数,是选择 $k$ 个数并作积的最大 roundness 值。 ## 样例解释 在第一个例子中,有三种选法。$[50,4]$ 的积是 $200$,roundness 值是 $2$;$[4,20]$ 的积是 $80$,roundness 值是 $1$;$[50,20]$ 的积是 $1000$,roundness 值是 $3$。 第二个例子中选法 $[15,16,25]$ 的积是 $6000$,roundness 值是 $3$。 第三个例子中所有的选法的积的 roundness 值都是 $0$。 translated by @poorpool

加入题单

上一题 下一题 算法标签: