Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
You do not need to search all valid numbers. The optimal is either the largest valid number with , or the smallest valid number with .
Work with the decimal string of . Numbers with fewer digits than 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 , look at the first position where it differs: the prefix must equal , digit must be , and the suffix should be filled with the largest allowed digit.
Similarly, for a same-length number to be larger than , choose the first differing digit , then fill the suffix with the smallest allowed digit. Try every possible first differing position whose prefix is already valid.
Compute two values: and . For , also check the best shorter number: length filled with the largest digit. For , also check the best longer number: first digit = smallest nonzero allowed digit, rest = smallest allowed digit. Answer .
The function is boring in the best possible way: among all valid , only the largest one matters; among all valid , only the smallest one matters.
So we only need:
and
Then the answer is:
ignoring if it does not exist.
The decimal representation has no leading zeroes, except the number itself, whose representation is 0. That little goblin is the only annoying edge case.
Let be the decimal string of , and let .
For valid positive numbers:
So for the best smaller number with fewer digits, we only need the maximum number of length :
where is the largest allowed digit. This is checked only if .
For the best larger number with more digits, we only need the minimum number of length :
where:
Now we need valid numbers with exactly digits.
Suppose the candidate first differs from at position .
Then:
For each possible , this gives the best candidate whose first difference is at . Take the maximum over all of them.
Also, if every digit of itself is allowed, then is valid and .
Same logic, flipped:
Take the minimum over all such candidates.
Again, if itself is valid, then .
When constructing a same-length candidate of length , the first digit cannot be .
For length , digit is fine, because it represents the number .
That is the whole trap. Not a dragon, just a raccoon with a knife.
There are only digits because , and .
For each test case, we try each digit position and both allowed digits:
which is effectively constant.
Memory usage is:
#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;
}