C. Ever-Hungry Krakozyabra

Codeforces

IDCF833C

Time1000ms

Memory256MB

Difficulty—

brute forcecombinatoricsgreedymath

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 \mathbb{N},\ L \leq n \leq R \} $. **Constraints** $ 1 \leq L \leq R \leq 10^{18} $ **Objective** Compute $ |S(L, R)| $, the number of distinct inedible tails produced by applying $ f $ to all integers in $ [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": "C. 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": "CF833C"
  },
  "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