{"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 digit _0_.\n\nIt is allowed to leave _a_ as it is.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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.\n\nThe number in the output should have exactly the same length as number _a_. It should be a permutation of digits of _a_.\n\n[samples]","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] (#cf_span[1 ≤ b ≤ 1018])。这些数没有前导零。保证答案存在。\n\n请输出一个最大的可能数，它是 #cf_span[a] 的数字的一个排列，且不超过 #cf_span[b]。答案不能有前导零。保证答案存在。\n\n输出的数必须与 #cf_span[a] 的长度完全相同，且是 #cf_span[a] 的数字的一个排列。\n\n## Input\n\n第一行包含整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 1018])。第二行包含整数 #cf_span[b] (#cf_span[1 ≤ b ≤ 1018])。这些数没有前导零。保证答案存在。\n\n## Output\n\n请输出一个最大的可能数，它是 #cf_span[a] 的数字的一个排列，且不超过 #cf_span[b]。答案不能有前导零。保证答案存在。输出的数必须与 #cf_span[a] 的长度完全相同，且是 #cf_span[a] 的数字的一个排列。\n\n[samples]","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 $ 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).\n\nLet $ \\mathcal{P}(S) $ denote the set of all permutations of $ S $ that form $ d $-digit numbers with no leading zero.\n\nDefine $ f: \\mathcal{P}(S) \\to \\mathbb{Z} $ as the function mapping each permutation to the integer it represents.\n\n**Objective:**  \nFind  \n$$\n\\max \\left\\{ x \\in \\mathcal{P}(S) \\mid x \\leq b \\right\\}\n$$\n\n**Constraints:**  \n- $ x $ must be a $ d $-digit number.  \n- $ x $ must be a permutation of the digits of $ a $.  \n- $ x $ must not have leading zeros.  \n- $ x \\leq b $.  \n- The solution is guaranteed to exist.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF915C","tags":["dp","greedy"],"sample_group":[["123\n222","213"],["3921\n10000","9321"],["4940\n5000","4940"]],"created_at":"2026-03-03 11:00:39"}}