{"problem":{"name":"B. Weird Rounding","description":{"content":"Polycarp is crazy about round numbers. He especially likes the numbers divisible by 10_k_. In the given number of _n_ Polycarp wants to remove the least number of digits to get a number that is divis","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF779B"},"statements":[{"statement_type":"Markdown","content":"Polycarp is crazy about round numbers. He especially likes the numbers divisible by 10_k_.\n\nIn the given number of _n_ Polycarp wants to remove the least number of digits to get a number that is divisible by 10_k_. For example, if _k_ = 3, in the number _30020_ it is enough to delete a single digit (_2_). In this case, the result is _3000_ that is divisible by 103 = 1000.\n\nWrite a program that prints the minimum number of digits to be deleted from the given integer number _n_, so that the result is divisible by 10_k_. The result should not start with the unnecessary leading zero (i.e., zero can start only the number _0_, which is required to be written as exactly one digit).\n\nIt is guaranteed that the answer exists.\n\n## Input\n\nThe only line of the input contains two integer numbers _n_ and _k_ (0 ≤ _n_ ≤ 2 000 000 000, 1 ≤ _k_ ≤ 9).\n\nIt is guaranteed that the answer exists. All numbers in the input are written in traditional notation of integers, that is, without any extra leading zeros.\n\n## Output\n\nPrint _w_ — the required minimal number of digits to erase. After removing the appropriate _w_ digits from the number _n_, the result should have a value that is divisible by 10_k_. The result can start with digit _0_ in the single case (the result is zero and written by exactly the only digit _0_).\n\n[samples]\n\n## Note\n\nIn the example 2 you can remove two digits: 1 and any 0. The result is number 0 which is divisible by any number.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Polycarp 对圆数非常着迷。他尤其喜欢能被 $10^k$ 整除的数。\n\n给定一个数 $n$，Polycarp 希望删除最少数量的数字，使得剩余的数能被 $10^k$ 整除。例如，当 $k = 3$ 时，在数字 _30020_ 中，只需删除一个数字（_2_），结果为 _3000_，它能被 $10^3 = 1000$ 整除。\n\n请编写一个程序，输出从给定整数 $n$ 中删除的最少数字个数，使得结果能被 $10^k$ 整除。结果不应包含不必要的前导零（即，只有数字 _0_ 可以以零开头，且必须恰好用一位数字 _0_ 表示）。\n\n题目保证答案存在。\n\n输入仅一行，包含两个整数 $n$ 和 $k$（$0 ≤ n ≤ 2 000 000 000$，$1 ≤ k ≤ 9$）。\n\n题目保证答案存在。输入的所有数字均采用传统整数表示法，即没有多余的前导零。\n\n请输出 $w$ —— 所需删除的最少数字个数。从数字 $n$ 中移除适当的 $w$ 个数字后，结果的值应能被 $10^k$ 整除。仅在结果为零的情况下，结果可以以数字 _0_ 开头（此时必须恰好用一位数字 _0_ 表示）。\n\n## Input\n\n输入仅一行，包含两个整数 $n$ 和 $k$（$0 ≤ n ≤ 2 000 000 000$，$1 ≤ k ≤ 9$）。题目保证答案存在。输入的所有数字均采用传统整数表示法，即没有多余的前导零。\n\n## Output\n\n请输出 $w$ —— 所需删除的最少数字个数。从数字 $n$ 中移除适当的 $w$ 个数字后，结果的值应能被 $10^k$ 整除。仅在结果为零的情况下，结果可以以数字 _0_ 开头（此时必须恰好用一位数字 _0_ 表示）。\n\n[samples]\n\n## Note\n\n在第二个例子中，你可以删除两个数字：1 和任意一个 0。结果是数字 0，它可以被任何数整除。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $ be the given integer (in decimal representation).  \nLet $ k \\in \\{1, 2, \\dots, 9\\} $ be given.  \nLet $ d $ be the number of digits in the decimal representation of $ n $.  \nLet $ D = (d_1, d_2, \\dots, d_d) $ be the sequence of digits of $ n $, where $ d_1 $ is the most significant digit.\n\n**Constraints**  \n1. $ 0 \\leq n \\leq 2{,}000{,}000{,}000 $  \n2. $ 1 \\leq k \\leq 9 $  \n3. The result after deletion must be divisible by $ 10^k $.  \n4. The result must not have unnecessary leading zeros: it may be \"0\" (single digit), but not \"00...\", \"01\", etc.\n\n**Objective**  \nFind the minimum number $ w \\in \\mathbb{Z}_{\\geq 0} $ such that there exists a subsequence $ S $ of $ D $ of length $ d - w $, forming a number $ m $ satisfying:  \n- $ m \\equiv 0 \\pmod{10^k} $,  \n- $ m $ has no leading zeros except when $ m = 0 $.  \n\nOutput $ w $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF779B","tags":["brute force","greedy"],"sample_group":[["30020 3","1"],["100 9","2"],["10203049 2","3"]],"created_at":"2026-03-03 11:00:39"}}