E. Ever-Hungry Krakozyabra

Codeforces

IDCF834E

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

<center>![image](https://espresso.codeforces.com/f18a789560bd388b92b0720eedab0a350e16fcd1.png)</center>Recently, a wild Krakozyabra appeared at Jelly Castle. It is, truth to be said, always eager to have something for dinner. Its favorite meal is natural numbers (typically served with honey sauce), or, to be more precise, the zeros in their corresponding decimal representations. As for other digits, Krakozyabra dislikes them; moreover, they often cause it indigestion! So, as a necessary precaution, Krakozyabra prefers to sort the digits of a number in non-descending order before proceeding to feast. Then, the leading zeros of the resulting number are eaten and the remaining part is discarded as an _inedible tail_. For example, if Krakozyabra is to have the number 57040 for dinner, its _inedible tail_ would be the number 457. Slastyona is not really fond of the idea of Krakozyabra living in her castle. Hovewer, her natural hospitality prevents her from leaving her guest without food. Slastyona has a range of natural numbers from _L_ to _R_, which she is going to feed the guest with. Help her determine how many distinct _inedible tails_ are going to be discarded by Krakozyabra by the end of the dinner. ## Input In the first and only string, the numbers _L_ and _R_ are given – the boundaries of the range (1 ≤ _L_ ≤ _R_ ≤ 1018). ## Output Output the sole number – the answer for the problem. [samples] ## Note In the first sample case, the _inedible tails_ are the numbers from 1 to 9. Note that 10 and 1 have the same _inedible tail_ – the number 1. In the second sample case, each number has a unique _inedible tail_, except for the pair 45, 54. The answer to this sample case is going to be (57 - 40 + 1) - 1 = 17.

最近，一只野生的克拉科扎布拉出现在果冻城堡。说真的，它总是渴望吃点东西。它最喜欢的食物是自然数（通常配蜂蜜酱），更准确地说，是这些数的十进制表示中的零。至于其他数字，克拉科扎布拉非常讨厌它们；而且，它们常常导致它消化不良！因此，作为必要的预防措施，克拉科扎布拉在进餐前会将数字的各位按非降序排列。然后，它会吃掉所得数字的前导零，其余部分则被丢弃为一个_不可食用的尾巴_。例如，如果克拉科扎布拉要吃数字 #cf_span[57040]，它的_不可食用的尾巴_就是数字 #cf_span[457]。斯拉斯托娅并不喜欢克拉科扎布拉住在她的城堡里。然而，她天生的款待之心使她不能让客人挨饿。斯拉斯托娅有一段从 #cf_span[L] 到 #cf_span[R] 的自然数范围，她将用这段范围的食物喂养客人。请帮助她确定，在晚餐结束时，克拉科扎布拉将丢弃多少个不同的_不可食用的尾巴_。在第一行且仅有一行中，给出数字 #cf_span[L] 和 #cf_span[R] —— 范围 #cf_span[(1 ≤ L ≤ R ≤ 10^{18})] 的边界。输出一个单独的数字 —— 本题的答案。在第一个样例中，_不可食用的尾巴_ 是从 #cf_span[1] 到 #cf_span[9] 的数字。注意，#cf_span[10] 和 #cf_span[1] 具有相同的_不可食用的尾巴_ —— 数字 #cf_span[1]。在第二个样例中，每个数都有唯一的_不可食用的尾巴_，除了数对 #cf_span[45, 54]。该样例的答案为 #cf_span[(57 - 40 + 1) - 1 = 17]。 ## Input 在第一行且仅有一行中，给出数字 #cf_span[L] 和 #cf_span[R] —— 范围 #cf_span[(1 ≤ L ≤ R ≤ 10^{18})] 的边界。 ## Output 输出一个单独的数字 —— 本题的答案。 [samples] ## Note 在第一个样例中，_不可食用的尾巴_ 是从 #cf_span[1] 到 #cf_span[9] 的数字。注意，#cf_span[10] 和 #cf_span[1] 具有相同的_不可食用的尾巴_ —— 数字 #cf_span[1]。在第二个样例中，每个数都有唯一的_不可食用的尾巴_，除了数对 #cf_span[45, 54]。该样例的答案为 #cf_span[(57 - 40 + 1) - 1 = 17]。

**Definitions** Let $ f: \mathbb{N} \to \mathbb{N} $ be the function that maps a natural number $ n $ to its *inedible tail*, defined as follows: - Sort the decimal digits of $ n $ in non-decreasing order. - Remove all leading zeros from the resulting digit sequence. - Interpret the remaining digit sequence as a natural number (if empty, result is 0, but since $ n \geq 1 $, result is always $ \geq 1 $). Let $ S(L, R) = \{ f(n) \mid n \in [L, R] \cap \mathbb{N} \} $ be the set of distinct inedible tails produced by numbers in the range $[L, R]$. **Constraints** $ 1 \leq L \leq R \leq 10^{18} $ **Objective** Compute $ |S(L, R)| $, the number of distinct values in the image of $ f $ over $[L, R]$.

Samples

Input #1

1 10

Output #1

Input #2

40 57

Output #2

Input #3

157 165

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Ever-Hungry Krakozyabra",
    "description": {
      "content": "<center>![image](https://espresso.codeforces.com/f18a789560bd388b92b0720eedab0a350e16fcd1.png)</center>Recently, a wild Krakozyabra appeared at Jelly Castle. It is, truth to be said, always eager to h",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF834E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "<center>![image](https://espresso.codeforces.com/f18a789560bd388b92b0720eedab0a350e16fcd1.png)</center>Recently, a wild Krakozyabra appeared at Jelly Castle. It is, truth to be said, always eager to h...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "最近，一只野生的克拉科扎布拉出现在果冻城堡。说真的，它总是渴望吃点东西。\n\n它最喜欢的食物是自然数（通常配蜂蜜酱），更准确地说，是这些数的十进制表示中的零。至于其他数字，克拉科扎布拉非常讨厌它们；而且，它们常常导致它消化不良！因此，作为必要的预防措施，克拉科扎布拉在进餐前会将数字的各位按非降序排列。然后，它会吃掉所得数字的前导零，其余部分则被丢弃为一个_不可食用的尾巴_。\n\n例如，如果克拉科扎布拉...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f: \\mathbb{N} \\to \\mathbb{N} $ be the function that maps a natural number $ n $ to its *inedible tail*, defined as follows:  \n- Sort the decimal digits of $ n $ in non-decreasi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments