Codeforce 915C Permute Digits

Posted on | In | 阅读

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.

Examples

input

1
2
123
222

output

1
213

input

1
2
3921
10000

output

1
9321

input

1
2
4940
5000

output

1
4940
  • b一定不短于a
  • 如果b比a长，直接降序排列a
  • 如果一样长
    • 先统计a中数字的个数
    • 对于每一位b，都找不比b大的匹配，一旦有一位匹配后小于b的那位，之后就可以从最大的开始降序匹配
    • 如果有一位无法匹配小于等于b的那位，那么就回退一位，匹配小于b的，这样后面就可以不受约束

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iomanip>

using namespace std;

bool cmp(char a, char b)
{
    return a > b;
}

int main()
{
    char str1[20];
    char str2[20];
    char tmp;
    int arr[15];

    while(~scanf("%s", str1))
    {
        memset(arr, 0, sizeof(arr));
        getchar();
        scanf("%s", str2);
        getchar();
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        if(len2 > len1)
        {
            sort(str1, str1+len1, cmp);
        }
        else
        {
            bool flag = false;
            for(int i = 0; i < len1; i++)
            {
                arr[str1[i] - '0']++;
                str1[i] = str2[i];
            }
            for(int i = 0; i < len2; i++)
            {
                int j;
                if(flag == false)
                    j = str1[i] - '0';
                else
                    j = 9;
                for(; j >= 0; j--)
                {
                    if(arr[j] > 0)
                    {
                        arr[j]--;
                        str1[i] = j+'0';
                        if(j < str2[i] - '0')
                            flag = true;
                        break;
                    }
                }
                if(j == -1 && flag == false)
                {
                    i--;
                    arr[str1[i]-'0']++;
                    str1[i]--;
                    i--;
                }
            }
        }
        printf("%s\n", str1);
    }
    return 0;
}