B. Weird Rounding

Codeforces

IDCF779B

Time1000ms

Memory256MB

Difficulty—

brute forcegreedy

English · Original

Chinese · Translation

Formal · Original

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 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. Write 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). It is guaranteed that the answer exists. ## Input The only line of the input contains two integer numbers _n_ and _k_ (0 ≤ _n_ ≤ 2 000 000 000, 1 ≤ _k_ ≤ 9). It 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. ## Output Print _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_). [samples] ## Note In the example 2 you can remove two digits: 1 and any 0. The result is number 0 which is divisible by any number.

Polycarp 对圆数非常着迷。他尤其喜欢能被 $10^k$ 整除的数。给定一个数 $n$，Polycarp 希望删除最少数量的数字，使得剩余的数能被 $10^k$ 整除。例如，当 $k = 3$ 时，在数字 _30020_ 中，只需删除一个数字（_2_），结果为 _3000_，它能被 $10^3 = 1000$ 整除。请编写一个程序，输出从给定整数 $n$ 中删除的最少数字个数，使得结果能被 $10^k$ 整除。结果不应包含不必要的前导零（即，只有数字 _0_ 可以以零开头，且必须恰好用一位数字 _0_ 表示）。题目保证答案存在。输入仅一行，包含两个整数 $n$ 和 $k$（$0 ≤ n ≤ 2 000 000 000$，$1 ≤ k ≤ 9$）。题目保证答案存在。输入的所有数字均采用传统整数表示法，即没有多余的前导零。请输出 $w$ —— 所需删除的最少数字个数。从数字 $n$ 中移除适当的 $w$ 个数字后，结果的值应能被 $10^k$ 整除。仅在结果为零的情况下，结果可以以数字 _0_ 开头（此时必须恰好用一位数字 _0_ 表示）。 ## Input 输入仅一行，包含两个整数 $n$ 和 $k$（$0 ≤ n ≤ 2 000 000 000$，$1 ≤ k ≤ 9$）。题目保证答案存在。输入的所有数字均采用传统整数表示法，即没有多余的前导零。 ## Output 请输出 $w$ —— 所需删除的最少数字个数。从数字 $n$ 中移除适当的 $w$ 个数字后，结果的值应能被 $10^k$ 整除。仅在结果为零的情况下，结果可以以数字 _0_ 开头（此时必须恰好用一位数字 _0_ 表示）。 [samples] ## Note 在第二个例子中，你可以删除两个数字：1 和任意一个 0。结果是数字 0，它可以被任何数整除。

**Definitions** Let $ n \in \mathbb{Z}_{\geq 0} $ be the given integer (in decimal representation). Let $ k \in \{1, 2, \dots, 9\} $ be given. Let $ d $ be the number of digits in the decimal representation of $ n $. Let $ D = (d_1, d_2, \dots, d_d) $ be the sequence of digits of $ n $, where $ d_1 $ is the most significant digit. **Constraints** 1. $ 0 \leq n \leq 2{,}000{,}000{,}000 $ 2. $ 1 \leq k \leq 9 $ 3. The result after deletion must be divisible by $ 10^k $. 4. The result must not have unnecessary leading zeros: it may be "0" (single digit), but not "00...", "01", etc. **Objective** Find 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: - $ m \equiv 0 \pmod{10^k} $, - $ m $ has no leading zeros except when $ m = 0 $. Output $ w $.

Samples

Input #1

30020 3

Output #1

Input #2

100 9

Output #2

Input #3

10203049 2

Output #3

API Response (JSON)

{
  "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 divis...",
      "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$ 中删除的最少数字个数，使得结...",
      "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 re...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments