c++. без комментариев

cpp
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;

i128 to128(const string& s) {
    i128 x = 0;
    for (char c : s) x = x * 10 + (c - '0');
    return x;
}

void print128(i128 x) {
    if (x == 0) {
        cout << 0 << '\n';
        return;
    }
    string s;
    while (x > 0) {
        s.push_back(char('0' + x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s << '\n';
}

string normalize(string s) {
    int p = 0;
    while (p + 1 < (int)s.size() && s[p] == '0') p++;
    return s.substr(p);
}

string minLen(const vector<int>& d, int len) {
    if (len <= 0) return "";
    if (len == 1) return string(1, char('0' + d[0]));

    int first = -1;
    for (int x : d) {
        if (x != 0) {
            first = x;
            break;
        }
    }
    if (first == -1) return "";

    string res;
    res.push_back(char('0' + first));
    res.append(len - 1, char('0' + d[0]));
    return res;
}

string maxLen(const vector<int>& d, int len) {
    if (len <= 0) return "";
    if (len == 1) return string(1, char('0' + d.back()));

    int first = -1;
    for (int i = (int)d.size() - 1; i >= 0; i--) {
        if (d[i] != 0) {
            first = d[i];
            break;
        }
    }
    if (first == -1) return "";

    string res;
    res.push_back(char('0' + first));
    res.append(len - 1, char('0' + d.back()));
    return res;
}

bool okLead(int x, int pos, int len) {
    return pos > 0 || len == 1 || x != 0;
}

string lowerSame(const string& s, const vector<int>& d) {
    int len = s.size();
    string res(len, '0');

    for (int i = 0; i < len; i++) {
        int lim = s[i] - '0';
        int best = -1;

        for (int j = (int)d.size() - 1; j >= 0; j--) {
            if (d[j] <= lim && okLead(d[j], i, len)) {
                best = d[j];
                break;
            }
        }

        if (best == -1) {
            for (int j = i - 1; j >= 0; j--) {
                int cur = res[j] - '0';
                int repl = -1;

                for (int k = (int)d.size() - 1; k >= 0; k--) {
                    if (d[k] < cur && okLead(d[k], j, len)) {
                        repl = d[k];
                        break;
                    }
                }

                if (repl != -1) {
                    res[j] = char('0' + repl);
                    for (int k = j + 1; k < len; k++) {
                        res[k] = char('0' + d.back());
                    }
                    return res;
                }
            }
            return "";
        }

        res[i] = char('0' + best);

        if (best < lim) {
            for (int j = i + 1; j < len; j++) {
                res[j] = char('0' + d.back());
            }
            return res;
        }
    }

    return res;
}

string upperSame(const string& s, const vector<int>& d) {
    int len = s.size();
    string res(len, '0');

    for (int i = 0; i < len; i++) {
        int lim = s[i] - '0';
        int best = -1;

        for (int x : d) {
            if (x >= lim && okLead(x, i, len)) {
                best = x;
                break;
            }
        }

        if (best == -1) {
            for (int j = i - 1; j >= 0; j--) {
                int cur = res[j] - '0';
                int repl = -1;

                for (int x : d) {
                    if (x > cur && okLead(x, j, len)) {
                        repl = x;
                        break;
                    }
                }

                if (repl != -1) {
                    res[j] = char('0' + repl);
                    for (int k = j + 1; k < len; k++) {
                        res[k] = char('0' + d[0]);
                    }
                    return res;
                }
            }
            return "";
        }

        res[i] = char('0' + best);

        if (best > lim) {
            for (int j = i + 1; j < len; j++) {
                res[j] = char('0' + d[0]);
            }
            return res;
        }
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        string a;
        int n;
        cin >> a >> n;

        a = normalize(a);

        vector<int> d(n);
        for (int& x : d) cin >> x;
        sort(d.begin(), d.end());

        int len = a.size();
        i128 av = to128(a);
        i128 ans = -1;

        string lo = lowerSame(a, d);
        if (lo.empty()) {
            for (int l = len - 1; l >= 1; l--) {
                lo = maxLen(d, l);
                if (!lo.empty()) break;
            }
        }

        string hi = upperSame(a, d);
        if (hi.empty()) {
            hi = minLen(d, len + 1);
        }

        if (!lo.empty()) {
            i128 bv = to128(lo);
            ans = av >= bv ? av - bv : bv - av;
        }

        if (!hi.empty()) {
            i128 bv = to128(hi);
            i128 diff = av >= bv ? av - bv : bv - av;
            if (ans == -1 || diff < ans) ans = diff;
        }

        print128(ans);
    }

    return 0;
}