C. Really Big Numbers

Codeforces

IDCF817C

Time1000ms

Memory256MB

Difficulty—

binary searchbrute forcedpmath

English · Original

Chinese · Translation

Formal · Original

Ivan likes to learn different things about numbers, but he is especially interested in _really big_ numbers. Ivan thinks that a positive integer number _x_ is _really big_ if the difference between _x_ and the sum of its digits (in decimal representation) is not less than _s_. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are — in fact, he needs to calculate the quantity of _really big_ numbers that are not greater than _n_. Ivan tried to do the calculations himself, but soon realized that it's too difficult for him. So he asked you to help him in calculations. ## Input The first (and the only) line contains two integers _n_ and _s_ (1 ≤ _n_, _s_ ≤ 1018). ## Output Print one integer — the quantity of _really big_ numbers that are not greater than _n_. [samples] ## Note In the first example numbers 10, 11 and 12 are _really big_. In the second example there are no _really big_ numbers that are not greater than 25 (in fact, the first _really big_ number is 30: 30 - 3 ≥ 20). In the third example 10 is the only _really big_ number (10 - 1 ≥ 9).

Ivan 喜欢学习关于数字的各种知识，但他尤其对 _真正大_ 的数字感兴趣。Ivan 认为一个正整数 #cf_span[x] 是 _真正大_ 的，当且仅当 #cf_span[x] 与其各位数字之和（十进制表示）的差不小于 #cf_span[s]。为了证明这类数字可能具有不同的特殊性质，他需要知道这类数字有多稀有（或不稀有）——实际上，他需要计算不超过 #cf_span[n] 的 _真正大_ 数字的数量。 Ivan 试图自己进行计算，但很快意识到这对他来说太难了。因此他请求你帮助他进行计算。第一行（也是唯一一行）包含两个整数 #cf_span[n] 和 #cf_span[s]（#cf_span[1 ≤ n, s ≤ 1018]）。请输出一个整数——不超过 #cf_span[n] 的 _真正大_ 数字的数量。在第一个例子中，数字 #cf_span[10]、#cf_span[11] 和 #cf_span[12] 是 _真正大_ 的。在第二个例子中，没有不超过 #cf_span[25] 的 _真正大_ 数字（事实上，第一个 _真正大_ 数字是 #cf_span[30]：#cf_span[30 - 3 ≥ 20]）。在第三个例子中，#cf_span[10] 是唯一的 _真正大_ 数字（#cf_span[10 - 1 ≥ 9]）。 ## Input 第一行（也是唯一一行）包含两个整数 #cf_span[n] 和 #cf_span[s]（#cf_span[1 ≤ n, s ≤ 1018]）。 ## Output 请输出一个整数——不超过 #cf_span[n] 的 _真正大_ 数字的数量。 [samples] ## Note 在第一个例子中，数字 #cf_span[10]、#cf_span[11] 和 #cf_span[12] 是 _真正大_ 的。在第二个例子中，没有不超过 #cf_span[25] 的 _真正大_ 数字（事实上，第一个 _真正大_ 数字是 #cf_span[30]：#cf_span[30 - 3 ≥ 20]）。在第三个例子中，#cf_span[10] 是唯一的 _真正大_ 数字（#cf_span[10 - 1 ≥ 9]）。

**Definitions** Let $ n, s \in \mathbb{Z}^+ $ with $ 1 \leq n, s \leq 10^{18} $. For a positive integer $ x $, let $ d(x) $ denote the sum of its decimal digits. **Constraint** A positive integer $ x $ is *really big* if: $$ x - d(x) \geq s $$ **Objective** Compute the quantity of integers $ x $ such that: $$ 1 \leq x \leq n \quad \text{and} \quad x - d(x) \geq s $$

Samples

Input #1

12 1

Output #1

Input #2

25 20

Output #2

Input #3

10 9

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Really Big Numbers",
    "description": {
      "content": "Ivan likes to learn different things about numbers, but he is especially interested in _really big_ numbers. Ivan thinks that a positive integer number _x_ is _really big_ if the difference between _x",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF817C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan likes to learn different things about numbers, but he is especially interested in _really big_ numbers. Ivan thinks that a positive integer number _x_ is _really big_ if the difference between _x...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ivan 喜欢学习关于数字的各种知识，但他尤其对 _真正大_ 的数字感兴趣。Ivan 认为一个正整数 #cf_span[x] 是 _真正大_ 的，当且仅当 #cf_span[x] 与其各位数字之和（十进制表示）的差不小于 #cf_span[s]。为了证明这类数字可能具有不同的特殊性质，他需要知道这类数字有多稀有（或不稀有）——实际上，他需要计算不超过 #cf_span[n] 的 _真正大_ 数字的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, s \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, s \\leq 10^{18} $.  \nFor a positive integer $ x $, let $ d(x) $ denote the sum of its decimal digits.  \n\n**Constraint**  \nA positive int...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments