Permute Digits

time limit per test:1 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output

Problem Description

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 ≤ 10^18). The second line contains integer b (1 ≤ b ≤ 10^18). 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.

Sample Input

123
222
3921
10000
4940
5000

Sample Output

213
9321
4940

---

http://codeforces.com/contest...

---

Accepted Code

// Author : Weihao Long
// Created : 2018/01/15

#include "stdio.h"
#include "string.h"

#define ll long long

int main() {
    ll a, b;
    while (scanf("%lld%lld", &a, &b) != EOF) {
        char aa[20], bb[20];
        sprintf(aa, "%lld", a);
        sprintf(bb, "%lld", b);
        int lena = strlen(aa);
        int lenb = strlen(bb);
        if (lenb > lena) {
            for (int i = 1; i < lena; i++)
                for (int k = 0; k < lena - i; k++)
                    if (aa[k] < aa[k + 1]) {
                        char tmp = aa[k];
                        aa[k] = aa[k + 1];
                        aa[k + 1] = tmp;
                    }
        }
        else {
            int c[10] = { 0 };
            for (int i = 0; i < lena; i++)
                c[aa[i] - '0']++;
            ll ans = 0;
            for (int i = 0; i < lenb; i++) {
                int index = 0, flag = 0;
                for (int k = 9; k >= 0; k--) {
                    if (c[k] && k < bb[i] - '0') {
                        ans = ans * 10 + k;
                        c[k]--;
                        index = 1;
                        flag = 1;
                        break;
                    }
                    else if (c[k] && k == bb[i] - '0') {
                        ans = ans * 10 + k;
                        c[k]--;
                        index = 1;
                        break;
                    }
                }
                while (!index) {
                    i--;
                    int last = ans % 10;
                    c[last]++;
                    ans /= 10;
                    for (int k = last - 1; k >= 0; k--)
                        if (c[k]) {
                            ans = ans * 10 + k;
                            c[k]--;
                            index = 1;
                            flag = 1;
                            break;
                        }
                }
                if (flag || i == lenb - 1) {
                    for (;;) {
                        int k;
                        for (k = 9; k >= 0; k--) {
                            if (c[k]) {
                                ans = ans * 10 + k;
                                c[k]--;
                                break;
                            }
                        }
                        if (k == -1)
                            break;
                    }
                    sprintf(aa, "%lld", ans);
                    break;
                }
            }
        }
        puts(aa);
    }
    return 0;
}

Notes

题意：
输入两个数 a 和 b，你可以对 a 调整数字的顺序，要求调整后的 a 尽可能大，但同时要小于 b。

算法：
第一步：将 a 和 b 输出到字符串 aa 和 bb 中。
第二步：如果 a 的位数小于 b，那么只须将 a 的数字降序排列即可。
第三步：否则就是 a 的位数等于 b 的位数的情况。先统计 a 中各数字的个数。
第四步：以 b 为基准，从头扫到尾，从 a 中挑选合适的数字与之匹配。
第五步：若没有可匹配的，则回退，换小的数字。（重复执行此步直到找到可匹配的数字为止）