{"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 product of the selected numbers will be maximum possible.\n\n## Input\n\nThe first line contains two integer numbers _n_ and _k_ (1 ≤ _n_ ≤ 200, 1 ≤ _k_ ≤ _n_).\n\nThe second line contains _n_ space-separated integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 1018).\n\n## Output\n\nPrint maximal roundness of product of the chosen subset of length _k_.\n\n[samples]\n\n## Note\n\nIn 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_.\n\nIn the second example subset \\[15, 16, 25\\] has product _6000_, _roundness_ _3_.\n\nIn the third example all subsets has product with _roundness_ _0_.","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_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 1018]）。\n\n请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。\n\n在第一个例子中，有 _3_ 个包含 _2_ 个数的子集。#cf_span[[50, 4]] 的乘积为 _200_，其 _roundness_ 为 _2_；#cf_span[[4, 20]] 的乘积为 _80_，_roundness_ 为 _1_；#cf_span[[50, 20]] 的乘积为 _1000_，_roundness_ 为 _3_。\n\n在第二个例子中，子集 #cf_span[[15, 16, 25]] 的乘积为 _6000_，_roundness_ 为 _3_。\n\n在第三个例子中，所有子集的乘积的 _roundness_ 均为 _0_。\n\n## Input\n\n第一行包含两个整数 #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]）。\n\n## Output\n\n请输出所选长度为 #cf_span[k] 的子集的乘积的最大 _roundness_。\n\n[samples]\n\n## Note\n\n在第一个例子中，有 _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_。","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 any positive integer $ x $, define its *roundness* $ r(x) $ as the highest power of 10 dividing $ x $, i.e.,  \n$$\nr(x) = \\min(v_2(x), v_5(x)),\n$$  \nwhere $ v_p(x) $ denotes the exponent of prime $ p $ in the prime factorization of $ x $.  \n\nFor a subset $ S \\subseteq A $ with $ |S| = k $, define the roundness of the product as $ r\\left( \\prod_{a \\in S} a \\right) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200 $  \n2. $ 1 \\leq k \\leq n $  \n3. $ 1 \\leq a_i \\leq 10^{18} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nMaximize the roundness over all subsets of size $ k $:  \n$$\n\\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)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF837D","tags":["dp","math"],"sample_group":[["3 2\n50 4 20","3"],["5 3\n15 16 3 25 9","3"],["3 3\n9 77 13","0"]],"created_at":"2026-03-03 11:00:39"}}