English · Original
Chinese · Translation
Formal · Original
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.
## Input
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_ ≤ 1018).
## Output
Print maximal roundness of product of the chosen subset of length _k_.
[samples]
## Note
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_.
我们定义一个数的 _roundness_ 为其末尾零的个数。
你有一个包含 #cf_span[n] 个数的数组。你需要从中选择一个恰好包含 #cf_span[k] 个数的子集，使得所选数字乘积的 _roundness_ 最大。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200, 1 ≤ k ≤ n]）。
第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1018]）。
请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。
在第一个例子中，有 _3_ 个包含 _2_ 个数的子集。#cf_span[[50, 4]] 的乘积为 _200_，其 _roundness_ 为 _2_；#cf_span[[4, 20]] 的乘积为 _80_，_roundness_ 为 _1_；#cf_span[[50, 20]] 的乘积为 _1000_，_roundness_ 为 _3_。
在第二个例子中，子集 #cf_span[[15, 16, 25]] 的乘积为 _6000_，_roundness_ 为 _3_。
在第三个例子中，所有子集的乘积的 _roundness_ 均为 _0_。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200, 1 ≤ k ≤ n]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1018]）。
## Output
请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。
[samples]
## Note
在第一个例子中，有 _3_ 个包含 _2_ 个数的子集。#cf_span[[50, 4]] 的乘积为 _200_，其 _roundness_ 为 _2_；#cf_span[[4, 20]] 的乘积为 _80_，_roundness_ 为 _1_；#cf_span[[50, 20]] 的乘积为 _1000_，_roundness_ 为 _3_。在第二个例子中，子集 #cf_span[[15, 16, 25]] 的乘积为 _6000_，_roundness_ 为 _3_。在第三个例子中，所有子集的乘积的 _roundness_ 均为 _0_。
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 200 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ 1 \leq a_i \leq 10^{18} $.
For any positive integer $ x $, define its *roundness* $ r(x) $ as the highest power of 10 dividing $ x $, i.e.,
$$
r(x) = \min(v_2(x), v_5(x)),
$$
where $ v_p(x) $ denotes the exponent of prime $ p $ in the prime factorization of $ x $.
For a subset $ S \subseteq A $ with $ |S| = k $, define the roundness of the product as $ r\left( \prod_{a \in S} a \right) $.
**Constraints**
1. $ 1 \leq n \leq 200 $
2. $ 1 \leq k \leq n $
3. $ 1 \leq a_i \leq 10^{18} $ for all $ i \in \{1, \dots, n\} $
**Objective**
Maximize the roundness over all subsets of size $ k $:
$$
\max_{\substack{S \subseteq \{1, \dots, n\} \\ |S| = k}} r\left( \prod_{i \in S} a_i \right) = \max_{\substack{S \subseteq \{1, \dots, n\} \\ |S| = k}} \min\left( \sum_{i \in S} v_2(a_i), \sum_{i \in S} v_5(a_i) \right)
$$
API Response (JSON)
{
"problem": {
"name": "D. Round Subset",
"description": {
"content": "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 prod",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF837D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Let's call the _roundness_ of the number the number of zeros to which it ends.\n\nYou have an array of _n_ numbers. You need to choose a subset of exactly _k_ numbers so that the _roundness_ of the prod...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "我们定义一个数的 _roundness_ 为其末尾零的个数。\n\n你有一个包含 #cf_span[n] 个数的数组。你需要从中选择一个恰好包含 #cf_span[k] 个数的子集，使得所选数字乘积的 _roundness_ 最大。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200, 1 ≤ k ≤ n]）。\n\n第二行包含 #cf_sp...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 200 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ 1 \\leq a_i \\leq 10^{18} $. \n\nFor an...",
"is_translate": false,
"language": "Formal"
}
]
}