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.
Don’t overthink the decimal digit condition. A number is good iff, after deleting duplicate digits, there are at most two digits left.
Since and , the product fits easily in long long. So checking whether a candidate works is cheap.
There are not many good numbers up to . For each length, choose one or two allowed digits, and generate all digit strings using only them.
A simpler way: just iterate all integers from to ? Nope, that’s cooked. But iterating all good integers is tiny: about scale, not .
Precompute every good , then for each given , scan that list until good(x * y) is true. The statement guarantees a solution exists, and this search space is small enough.
Key Idea
We need a good number such that is also good.
The trick is that “good” is an extremely restrictive decimal property. There are a billion integers up to , but only a small number of them use at most two distinct digits. So instead of trying to derive some cursed digit-carry formula, we can generate all possible good candidates and test them.
That’s the whole play. Brute force, but only over the numbers that matter. Very legal, very clean.
Checking Goodness
A number is good if its decimal representation contains at most two distinct digits.
For a number , mark every digit that appears. If more than two digits appear, it is not good.
Also,
so
which fits comfortably inside long long.
Generating Good Candidates
Every valid has at most two different digits. Its length is at most , because itself has digits and is allowed.
We recursively build numbers using a chosen set of one or two digits:
After generating, sort and remove duplicates.
This is small. Brute forcing all integers up to is insane; brute forcing all good integers is totally fine.
Answering a Test Case
For each input :
The problem accepts any valid answer, so we do not need the smallest one.
Why This Works
Our precomputation contains every possible good in the allowed range .
So if an answer exists, it is in the candidate list. For each candidate, is already good, and we explicitly check that is good.
The statement guarantees a solution exists, so the scan will find one.
Complexity
Let be the number of generated good candidates. It is only tens of thousands.
Per test case, the time is
with a tiny constant. Memory is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
bool good(ll n) {
bool seen[10] = {};
int cnt = 0;
while (n > 0) {
int d = n % 10;
if (!seen[d]) {
seen[d] = true;
cnt++;
}
n /= 10;
}
return cnt <= 2;
}
int main() {
setIO();
vector<ll> cand;
for (int a = 0; a <= 9; a++) {
for (int b = a; b <= 9; b++) {
vector<int> digs = {a};
if (b != a) digs.push_back(b);
function<void(ll)> gen = [&](ll cur) {
if (cur > 1000000000LL) return;
if (cur >= 2) cand.push_back(cur);
for (int d : digs) {
if (cur == 0 && d == 0) continue;
gen(cur * 10 + d);
}
};
gen(0);
}
}
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
int t;
cin >> t;
while (t--) {
ll x;
cin >> x;
for (ll y : cand) {
if (good(x * y)) {
cout << y << '\n';
break;
}
}
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
bool good(ll n) {
bool seen[10] = {};
int cnt = 0;
while (n > 0) {
int d = n % 10;
if (!seen[d]) {
seen[d] = true;
cnt++;
}
n /= 10;
}
return cnt <= 2;
}
int main() {
setIO();
vector<ll> cand;
for (int a = 0; a <= 9; a++) {
for (int b = a; b <= 9; b++) {
vector<int> digs = {a};
if (b != a) digs.push_back(b);
function<void(ll)> gen = [&](ll cur) {
if (cur > 1000000000LL) return;
if (cur >= 2) cand.push_back(cur);
for (int d : digs) {
if (cur == 0 && d == 0) continue;
gen(cur * 10 + d);
}
};
gen(0);
}
}
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
int t;
cin >> t;
while (t--) {
ll x;
cin >> x;
for (ll y : cand) {
if (good(x * y)) {
cout << y << '\n';
break;
}
}
}
}