2228C1UnreviewedunratedGPT-5.5 (high)

Cirno and Number (Easy Version)

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

binary search brute force dp greedy implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

You do not need to search all valid numbers. The optimal $b$ is either the largest valid number with $b \le a$ , or the smallest valid number with $b \ge a$ .

Work with the decimal string $s$ of $a$ . Numbers with fewer digits than $s$ are automatically smaller; numbers with more digits are automatically larger — just remember that leading zeroes are not part of decimal representation.

For a same-length number to be smaller than $s$ , look at the first position $i$ where it differs: the prefix must equal $s$ , digit $i$ must be $< s_i$ , and the suffix should be filled with the largest allowed digit.

Similarly, for a same-length number to be larger than $s$ , choose the first differing digit $> s_i$ , then fill the suffix with the smallest allowed digit. Try every possible first differing position $i$ whose prefix is already valid.

Compute two values: $L=\max\{b\le a\}$ and $R=\min\{b\ge a\}$ . For $L$ , also check the best shorter number: length $|s|-1$ filled with the largest digit. For $R$ , also check the best longer number: first digit = smallest nonzero allowed digit, rest = smallest allowed digit. Answer $\min(a-L, R-a)$ .

Key idea

The function $|a-b|$ is boring in the best possible way: among all valid $b<a$ , only the largest one matters; among all valid $b>a$ , only the smallest one matters.

So we only need:

L = \max\{b \mid b \le a,\ b \text{ is valid}\}

and

R = \min\{b \mid b \ge a,\ b \text{ is valid}\}.

Then the answer is:

\min(a-L,\ R-a),

ignoring $L$ if it does not exist.

The decimal representation has no leading zeroes, except the number $0$ itself, whose representation is 0. That little goblin is the only annoying edge case.

Comparing by length

Let $s$ be the decimal string of $a$ , and let $m=|s|$ .

For valid positive numbers:

any number with fewer than $m$ digits is smaller than $a$ ;
any number with more than $m$ digits is larger than $a$ .

So for the best smaller number with fewer digits, we only need the maximum number of length $m-1$ :

\underbrace{DD\ldots D}_{m-1\text{ digits}},

where $D$ is the largest allowed digit. This is checked only if $m>1$ .

For the best larger number with more digits, we only need the minimum number of length $m+1$ :

p\underbrace{qq\ldots q}_{m\text{ digits}},

where:

$p$ is the smallest nonzero allowed digit,
$q$ is the smallest allowed digit.

Same-length candidates

Now we need valid numbers with exactly $m$ digits.

Largest valid number $\le a$

Suppose the candidate first differs from $s$ at position $i$ .

Then:

positions $0,1,\ldots,i-1$ must equal $s$ and must all be allowed digits;
position $i$ must be an allowed digit strictly smaller than $s_i$ ;
the suffix should be as large as possible, so fill it with the largest allowed digit.

For each possible $i$ , this gives the best candidate whose first difference is at $i$ . Take the maximum over all of them.

Also, if every digit of $s$ itself is allowed, then $a$ is valid and $L=a$ .

Smallest valid number $\ge a$

Same logic, flipped:

prefix equals $s$ and is valid;
at position $i$ , choose the smallest allowed digit strictly greater than $s_i$ ;
fill the suffix with the smallest allowed digit.

Take the minimum over all such candidates.

Again, if $a$ itself is valid, then $R=a$ .

Leading zeroes

When constructing a same-length candidate of length $m>1$ , the first digit cannot be $0$ .

For length $1$ , digit $0$ is fine, because it represents the number $0$ .

That is the whole trap. Not a dragon, just a raccoon with a knife.

Complexity

There are only $m \le 18$ digits because $a \le 10^{17}$ , and $n=2$ .

For each test case, we try each digit position and both allowed digits:

O(mn) = O(18 \cdot 2),

which is effectively constant.

Memory usage is:

O(1).

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

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

bool validFirstDigit(int digit, int len) {
    return len == 1 || digit != 0;
}

ll largest_leq(ll a, const vector<int> &d, const array<bool, 10> &ok) {
    string s = to_string(a);
    int m = (int)s.size();
    ll best = -1;

    bool prefixValid = true;

    for (int i = 0; i < m; i++) {
        if (!prefixValid) break;

        int cur = s[i] - '0';
        int choose = -1;

        for (int x : d) {
            if (x < cur && validFirstDigit(x, m) || (x < cur && i > 0)) {
                choose = max(choose, x);
            }
        }

        // Cleaner leading-zero check: digit at position 0 of a multi-digit number cannot be 0.
        choose = -1;
        for (int x : d) {
            if (x < cur && (i > 0 || validFirstDigit(x, m))) {
                choose = max(choose, x);
            }
        }

        if (choose != -1) {
            string cand = s.substr(0, i);
            cand.push_back(char('0' + choose));
            cand.append(m - i - 1, char('0' + d.back()));
            best = max(best, valueOf(cand));
        }

        if (!ok[cur]) {
            prefixValid = false;
            break;
        }
    }

    if (prefixValid) best = max(best, a);

    // Best number with fewer digits: all digits are the maximum allowed digit.
    if (m > 1) {
        string cand(m - 1, char('0' + d.back()));
        best = max(best, valueOf(cand));
    }

    return best;
}

ll smallest_geq(ll a, const vector<int> &d, const array<bool, 10> &ok) {
    string s = to_string(a);
    int m = (int)s.size();
    const ll INF = LLONG_MAX;
    ll best = INF;

    bool prefixValid = true;

    for (int i = 0; i < m; i++) {
        if (!prefixValid) break;

        int cur = s[i] - '0';
        int choose = 10;

        for (int x : d) {
            if (x > cur && (i > 0 || validFirstDigit(x, m))) {
                choose = min(choose, x);
            }
        }

        if (choose != 10) {
            string cand = s.substr(0, i);
            cand.push_back(char('0' + choose));
            cand.append(m - i - 1, char('0' + d.front()));
            best = min(best, valueOf(cand));
        }

        if (!ok[cur]) {
            prefixValid = false;
            break;
        }
    }

    if (prefixValid) best = min(best, a);

    // Best number with more digits: smallest nonzero first digit, then smallest digit everywhere.
    int first = 10;
    for (int x : d) {
        if (x > 0) {
            first = x;
            break;
        }
    }

    string cand;
    cand.push_back(char('0' + first));
    cand.append(m, char('0' + d.front()));
    best = min(best, valueOf(cand));

    return best;
}

int main() {
    setIO();

    int T;
    cin >> T;

    while (T--) {
        ll a;
        int n;
        cin >> a >> n;

        vector<int> d(n);
        array<bool, 10> ok{};

        for (int i = 0; i < n; i++) {
            cin >> d[i];
            ok[d[i]] = true;
        }

        ll L = largest_leq(a, d, ok);
        ll R = smallest_geq(a, d, ok);

        ll ans = R - a;
        if (L != -1) ans = min(ans, a - L);

        cout << ans << '\n';
    }

    return 0;
}

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

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

bool validFirstDigit(int digit, int len) {
    return len == 1 || digit != 0;
}

ll largest_leq(ll a, const vector<int> &d, const array<bool, 10> &ok) {
    string s = to_string(a);
    int m = (int)s.size();
    ll best = -1;

    bool prefixValid = true;

    for (int i = 0; i < m; i++) {
        if (!prefixValid) break;

        int cur = s[i] - '0';
        int choose = -1;

        for (int x : d) {
            if (x < cur && validFirstDigit(x, m) || (x < cur && i > 0)) {
                choose = max(choose, x);
            }
        }

        // Cleaner leading-zero check: digit at position 0 of a multi-digit number cannot be 0.
        choose = -1;
        for (int x : d) {
            if (x < cur && (i > 0 || validFirstDigit(x, m))) {
                choose = max(choose, x);
            }
        }

        if (choose != -1) {
            string cand = s.substr(0, i);
            cand.push_back(char('0' + choose));
            cand.append(m - i - 1, char('0' + d.back()));
            best = max(best, valueOf(cand));
        }

        if (!ok[cur]) {
            prefixValid = false;
            break;
        }
    }

    if (prefixValid) best = max(best, a);

    // Best number with fewer digits: all digits are the maximum allowed digit.
    if (m > 1) {
        string cand(m - 1, char('0' + d.back()));
        best = max(best, valueOf(cand));
    }

    return best;
}

ll smallest_geq(ll a, const vector<int> &d, const array<bool, 10> &ok) {
    string s = to_string(a);
    int m = (int)s.size();
    const ll INF = LLONG_MAX;
    ll best = INF;

    bool prefixValid = true;

    for (int i = 0; i < m; i++) {
        if (!prefixValid) break;

        int cur = s[i] - '0';
        int choose = 10;

        for (int x : d) {
            if (x > cur && (i > 0 || validFirstDigit(x, m))) {
                choose = min(choose, x);
            }
        }

        if (choose != 10) {
            string cand = s.substr(0, i);
            cand.push_back(char('0' + choose));
            cand.append(m - i - 1, char('0' + d.front()));
            best = min(best, valueOf(cand));
        }

        if (!ok[cur]) {
            prefixValid = false;
            break;
        }
    }

    if (prefixValid) best = min(best, a);

    // Best number with more digits: smallest nonzero first digit, then smallest digit everywhere.
    int first = 10;
    for (int x : d) {
        if (x > 0) {
            first = x;
            break;
        }
    }

    string cand;
    cand.push_back(char('0' + first));
    cand.append(m, char('0' + d.front()));
    best = min(best, valueOf(cand));

    return best;
}

int main() {
    setIO();

    int T;
    cin >> T;

    while (T--) {
        ll a;
        int n;
        cin >> a >> n;

        vector<int> d(n);
        array<bool, 10> ok{};

        for (int i = 0; i < n; i++) {
            cin >> d[i];
            ok[d[i]] = true;
        }

        ll L = largest_leq(a, d, ok);
        ll R = smallest_geq(a, d, ok);

        ll ans = R - a;
        if (L != -1) ans = min(ans, a - L);

        cout << ans << '\n';
    }

    return 0;
}

View on Codeforces Back to the list

Cirno and Number (Easy Version)

Progressive nudges

Full explanation

Key idea

Comparing by length

Same-length candidates

Largest valid number $\le a$

Smallest valid number $\ge a$

Leading zeroes

Complexity

Generated C++

Cirno and Number (Easy Version)

Progressive nudges

Full explanation

Key idea

Comparing by length

Same-length candidates

Largest valid number ≤a\le a≤a

Smallest valid number ≥a\ge a≥a

Leading zeroes

Complexity

Generated C++

Largest valid number $\le a$

Smallest valid number $\ge a$