B. The number on the board

Codeforces

IDCF835B

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Some natural number was written on the board. Its sum of digits was not less than _k_. But you were distracted a bit, and someone changed this number to _n_, replacing some digits with others. It's known that the length of the number didn't change. You have to find the minimum number of digits in which these two numbers can differ. ## Input The first line contains integer _k_ (1 ≤ _k_ ≤ 109). The second line contains integer _n_ (1 ≤ _n_ < 10100000). There are no leading zeros in _n_. It's guaranteed that this situation is possible. ## Output Print the minimum number of digits in which the initial number and _n_ can differ. [samples] ## Note In the first example, the initial number could be 12. In the second example the sum of the digits of _n_ is not less than _k_. The initial number could be equal to _n_.

某自然数被写在了黑板上，其各位数字之和不小于 $k$。但你稍一分心，有人将这个数改成了 $n$，用其他数字替换了部分数位。已知数字的长度没有改变。你需要找出这两个数在最少多少个数位上可能不同。第一行包含整数 $k$（$1 ≤ k ≤ 10^9$）。第二行包含整数 $n$（$1 ≤ n < 10^{100000}$）。 $n$ 中没有前导零。保证这种情况是可能的。请输出初始数与 $n$ 可能不同的最少数位个数。在第一个例子中，初始数可能是 $12$。在第二个例子中，$n$ 的各位数字之和不小于 $k$，因此初始数可能等于 $n$。 ## Input 第一行包含整数 $k$（$1 ≤ k ≤ 10^9$）。第二行包含整数 $n$（$1 ≤ n < 10^{100000}$）。$n$ 中没有前导零。保证这种情况是可能的。 ## Output 请输出初始数与 $n$ 可能不同的最少数位个数。 [samples] ## Note 在第一个例子中，初始数可能是 $12$。在第二个例子中，$n$ 的各位数字之和不小于 $k$，因此初始数可能等于 $n$。

**Definitions** Let $ k \in \mathbb{Z} $ with $ 1 \leq k \leq 10^9 $ be the minimum required digit sum. Let $ n $ be a string of decimal digits representing a positive integer with no leading zeros, and let $ |n| $ denote its length. Let $ s(n) = \sum_{i=1}^{|n|} d_i $ be the sum of the decimal digits of $ n $, where $ d_i $ is the $ i $-th digit. **Constraints** 1. $ 1 \leq k \leq 10^9 $ 2. $ 1 \leq |n| < 10^{100000} $ (i.e., $ n $ is a very long decimal string) 3. $ n $ has no leading zeros. 4. It is guaranteed that there exists a number $ m $ with $ |m| = |n| $ and $ s(m) \geq k $, such that $ m $ differs from $ n $ in some digits. **Objective** Find the minimum number of digit positions in which $ n $ and some number $ m $ (with $ |m| = |n| $ and $ s(m) \geq k $) can differ. That is, minimize $ |\{ i \mid n_i \neq m_i \}| $, subject to $ s(m) \geq k $ and $ |m| = |n| $.

Samples

Input #1

3
11

Output #1

Input #2

3
99

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. The number on the board",
    "description": {
      "content": "Some natural number was written on the board. Its sum of digits was not less than _k_. But you were distracted a bit, and someone changed this number to _n_, replacing some digits with others. It's kn",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF835B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Some natural number was written on the board. Its sum of digits was not less than _k_. But you were distracted a bit, and someone changed this number to _n_, replacing some digits with others. It's kn...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "某自然数被写在了黑板上，其各位数字之和不小于 $k$。但你稍一分心，有人将这个数改成了 $n$，用其他数字替换了部分数位。已知数字的长度没有改变。\n\n你需要找出这两个数在最少多少个数位上可能不同。\n\n第一行包含整数 $k$（$1 ≤ k ≤ 10^9$）。\n\n第二行包含整数 $n$（$1 ≤ n < 10^{100000}$）。\n\n$n$ 中没有前导零。保证这种情况是可能的。\n\n请输出初始数与 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 10^9 $ be the minimum required digit sum.  \nLet $ n $ be a string of decimal digits representing a positive integer with no leading zero...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments