\(\color{#300000}{\text{1. Hướng dẫn <Cày trâu>}}\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Thử từng hoán vị và trong các hoán vị lớn hơn ta chọn cái nhỏ nhất

\(\color{#c01515}{\text{1. Tiếp cận <Cày trâu>}}\)

• \(\color{#f03030}{\text{<Cày trâu> <Nhánh cận>}}\) Xét số \(X\) như là một xâu các chữ số \(S\).

Ta sắp xếp \(S\) thành số nhỏ nhất (dãy tăng dần) \(T\) có thể và liên tục chọn hoán vị tiếp theo của \(T\) cho tới khi \(T > S\) thì xuất \(T\)

Trong C++ có 2 hàm là next_permutation (tìm hoán vị tiếp theo) prev_permutation (tìm hoán vị trước đó) có thể chạy trong \(O(n!)\) khi duyệt tất cả hoán vị

Nếu \(T\) không còn hoán vị nào nữa hay \(S\) là số lớn nhất (dãy giảm dần) thì xuất \(0\)

\(\color{#009933}{\text{1. Code tham khảo<Accepted> }}\): Xâu, Cày trâu

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n! \times n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    string s;
    cin >> s;

    string t = s;
    sort(all(t));
    while (t <= s) if (!next_permutation(all(t))) break;
    if (t > s) cout << t;
    else       cout << 0;
    return 0;
}

\(\color{#300000}{\text{2. Hướng dẫn <Xâu>}}\)

• \(\color{#903030}{\text{<Mục tiêu> }}\) xây dưng từng chữ số cho \(S\) tới khi nào \(S \geq X\) thì dừng (\(S\) tạo ra từ tập các chữ số của \(X\))

Xét vị trí \([i]\) mà mình xây được \(S[i] > X[i]\) thì mình thêm bao nhiêu số đằng sau \(S > X\) luôn thỏa nên ta đưa \(S\) nối với phần còn lại được sắp xếp nhỏ nhất (tăng dần) thì ta sẽ được một số \(S\) nhỏ nhất lớn hơn \(X\)

• \(\color{#903030}{\text{<Kết quả> }}\) Nếu \(S = X\) ta tìm hoán vị tiếp theo của \(S\). Nếu vẫn \(S \leq X\) thì xuất \(0\), ngược lại xuất \(S\)

\(\color{#c01515}{\text{2. Tiếp cận}}\)

• \(\color{#f03030}{\text{<Mục tiêu> }}\) Gọi \(fre[d]\) là số lần xuất hiện của chữ số \(d\) trong \(X\)

Mỗi lần thêm số \(d\) mình giảm \(fre[d]\). Mỗi lần gọi đệ quy mà kết quả \(false\) thì tăng lại \(fre[d]\) là không tồn tại cách thỏa mãn, ngược lại kết quả \(true\) là tìm được dãy thỏa mãn và return \(true\) luôn.

Nếu ta xây được toàn bộ chữ số, ta return \(true\)

Nếu như khi xây tới ô thứ \([i]\) mà không có \(X[i]\) nào để xây thêm, hay \(fre[X[i]] = 0\). Ta sẽ tìm một số \(d > X[i]\) để thêm vào.

Nếu tồn tại \(d > X[i]\), ta sẽ thêm \(d\) vào sau \(S\) rồi thêm lần lượt các \(X[t]\) số \(t\) vào \(S\) với \(t = 0 \rightarrow 9\). Sau đó return \(true\)

Nếu không tồn tại \(d > X[i]\) thì ta return \(false\) vì chỉ thêm được \(d < X[i]\) \(\Leftrightarrow\) \(S < X\)

Trong phần code, vì mình đang xây dần số \(S\) với độ dài lúc này là \(len\) thì phần tử tiếp theo mình thêm vào ở vị trí \([len]\)

• \(\color{#903030}{\text{<Kết quả> }}\)

Nếu \(S = X\) thì tìm hoán vị tiếp theo của \(S\)

Nếu sau đó \(S \leq X\) thì xuất \(0\)

Nếu sau đó \(S > X\) thì xuất từng chữ số của \(S\)

• \(\color{#903030}{\text{<Phân tích độ phức tạp> }}\) \(O(n + alphabet)\)

Vì mình chỉ có lựa chọn là thêm hoặc không thêm \(s[i]\) (hay trong code là \(v[len]\)) nên \(O(n)\)

Và trong vòng lặp mình nối thêm chữ số cho \(S\) khi tìm được \((d)\) thỏa mãn, thì các vòng lặp không lồng nhau nên \(O(n + alphabet)\) để nối các số \(t\) vào

\(\color{#009933}{\text{2. Code tham khảo<Accepted> }}\): Tiếp cận

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n + alphabet)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int n;
vector<int> v;
bool build(vector<int> &fre, vector<int> &s)
{
    int len = s.size();
    if (len >= n) return true;

    if (fre[v[len]])
    {
        /// Thu them chu so v[len] tu fre[]
        --fre[v[len]];
        s.push_back(v[len]);
        if (build(fre, s)) /// neu xay duong so S thi dung de quy
            return true;

        /// Tra lai chu so v[len] cho fre[]
        s.resize(len);
        ++fre[v[len]];
    }

    /// Tim kiem mot so (d > v[len]) de (S > X)
    for (int d = v[len] + 1; d <= 9; ++d)
    {
        if (fre[d]) /// tim duoc mot chu so (d) thoa man
        {
            /// Them so (d) vao S
            ++fre[d];
            s.push_back(d);

            for (int t = 0; t <= 9; ++t) /// Duyet lan luot cac chu so nho hon
                for (; fre[t] > 0; --fre[t]) /// Them fre[t] so (t) vao S
                    s.push_back(t);

            return true;
        }
    }

    return false;
}

int main()
{
    string s;
    cin >> s;

    n = s.size();
    v.resize(n); /// bien xau thanh so de tien xu li
    for (int i = 0; i < n; ++i)
        v[i] = s[i] - '0';

    /// Tinh tan so xuat hien
    vector<int> fre(10, 0);
    for (int i = 0; i < n; ++i)
        ++fre[v[i]];

    /// Tim hoan vi (res >= X)
    vector<int> res;
    build(fre, res);

    if (res == v) next_permutation(res.begin(), res.end());
    if (res <= v) cout << 0;
    else {
        for (int x : res) cout << x;
    }
    return 0;
}