C. Permute Digits

Codeforces

IDCF915C

Time1000ms

Memory256MB

Difficulty—

dpgreedy

English · Original

Chinese · Translation

Formal · Original

You are given two positive integer numbers _a_ and _b_. Permute (change order) of the digits of _a_ to construct maximal number not exceeding _b_. No number in input and/or output can start with the digit _0_. It is allowed to leave _a_ as it is. ## Input The first line contains integer _a_ (1 ≤ _a_ ≤ 1018). The second line contains integer _b_ (1 ≤ _b_ ≤ 1018). Numbers don't have leading zeroes. It is guaranteed that answer exists. ## Output Print the maximum possible number that is a permutation of digits of _a_ and is not greater than _b_. The answer can't have any leading zeroes. It is guaranteed that the answer exists. The number in the output should have exactly the same length as number _a_. It should be a permutation of digits of _a_. [samples]

给定两个正整数 #cf_span[a] 和 #cf_span[b]。请对 #cf_span[a] 的各位数字进行重排，构造一个不超过 #cf_span[b] 的最大数。输入和输出中的任何数都不能以数字 _0_ 开头。允许保持 #cf_span[a] 不变。第一行包含整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 1018])。第二行包含整数 #cf_span[b] (#cf_span[1 ≤ b ≤ 1018])。这些数没有前导零。保证答案存在。请输出一个最大的可能数，它是 #cf_span[a] 的数字的一个排列，且不超过 #cf_span[b]。答案不能有前导零。保证答案存在。输出的数必须与 #cf_span[a] 的长度完全相同，且是 #cf_span[a] 的数字的一个排列。 ## Input 第一行包含整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 1018])。第二行包含整数 #cf_span[b] (#cf_span[1 ≤ b ≤ 1018])。这些数没有前导零。保证答案存在。 ## Output 请输出一个最大的可能数，它是 #cf_span[a] 的数字的一个排列，且不超过 #cf_span[b]。答案不能有前导零。保证答案存在。输出的数必须与 #cf_span[a] 的长度完全相同，且是 #cf_span[a] 的数字的一个排列。 [samples]

Let $ a, b \in \mathbb{Z}^+ $ with $ 1 \leq a, b \leq 10^{18} $, and let $ d $ be the number of digits in $ a $ (i.e., $ d = \lfloor \log_{10} a \rfloor + 1 $). Let $ S $ be the multiset of digits of $ a $, i.e., $ S = \{ d_1, d_2, \dots, d_d \} $ where each $ d_i \in \{0,1,\dots,9\} $ and $ d_1 \neq 0 $ (since $ a $ has no leading zeros). Let $ \mathcal{P}(S) $ denote the set of all permutations of $ S $ that form $ d $-digit numbers with no leading zero. Define $ f: \mathcal{P}(S) \to \mathbb{Z} $ as the function mapping each permutation to the integer it represents. **Objective:** Find $$ \max \left\{ x \in \mathcal{P}(S) \mid x \leq b \right\} $$ **Constraints:** - $ x $ must be a $ d $-digit number. - $ x $ must be a permutation of the digits of $ a $. - $ x $ must not have leading zeros. - $ x \leq b $. - The solution is guaranteed to exist.

Samples

Input #1

123
222

Output #1

Input #2

3921
10000

Output #2

Input #3

4940
5000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "C. Permute Digits",
    "description": {
      "content": "You are given two positive integer numbers _a_ and _b_. Permute (change order) of the digits of _a_ to construct maximal number not exceeding _b_. No number in input and/or output can start with the d",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF915C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two positive integer numbers _a_ and _b_. Permute (change order) of the digits of _a_ to construct maximal number not exceeding _b_. No number in input and/or output can start with the d...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定两个正整数 #cf_span[a] 和 #cf_span[b]。请对 #cf_span[a] 的各位数字进行重排，构造一个不超过 #cf_span[b] 的最大数。输入和输出中的任何数都不能以数字 _0_ 开头。\n\n允许保持 #cf_span[a] 不变。\n\n第一行包含整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 1018])。第二行包含整数 #cf_span[b] (#c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq a, b \\leq 10^{18} $, and let $ d $ be the number of digits in $ a $ (i.e., $ d = \\lfloor \\log_{10} a \\rfloor + 1 $).\n\nLet $ S $ be the multiset of digits of...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments