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.
A digit-sum query is secretly a modulo query: if the answer in base is not , then .
Do not try to make every query a CRT query. A response of is also useful: it says , so small ranges can be handled by tiny brute-force decision trees.
The magic-looking bases are , , and . Their moduli are , , and , and .
After asking base , the branch is small enough to solve directly. If , the known value of leaves small groups that one more carefully chosen base separates.
For , ask base last. If it is not , CRT recovers . If it is , then , and the pair is already unique; the code precomputes that tiny table.
The first trap is thinking digit sums are just fuzzy information. They are not. They are modulo information wearing a fake mustache. For every base , if the query does not return , then
That is because , so every base- digit contributes exactly like its positional value modulo .
The second trap is pretending CRT alone solves the whole thing. It almost does, but small can make big-base queries return , and then the modulus information disappears. So the actual solution is a hybrid: use a couple of fixed bases, brute-force the tiny dangerous zones, and use CRT once all three modular answers are available. Not glamorous, but it absolutely gets the job done.
The Three Main Bases
Use these bases:
They are chosen because the moduli are pairwise coprime and
So if we receive real digit sums from all three of those bases, we know modulo a number larger than the whole search range. CRT gives exactly one possible . No guessing, no vibes.
Handling The Annoying Small Branches
First ask base .
If the answer is , then . This range is tiny, so we solve it with a precomputed two-query decision tree. The code asks base , then picks one final base that separates the remaining candidates. The program computes this table by brute force over only numbers.
Otherwise, , and we know . Now ask base .
If the answer is , then
For each possible value of , the candidate group inside this range is small. The code brute-forces a base whose digit-sum responses are injective on that group, asks it, and then scans to find the only match. This is the kind of brute force that is fine: it is tiny and done on constants.
Now suppose the base- answer is not . Then . Ask base .
If this third answer is , then
Here we use another finite fact: in this whole interval, the pair
is unique. The code precomputes a map from that pair to by scanning only about numbers. That is pocket change.
If the third answer is not , then all three modulo constraints are valid:
Their product is bigger than , so CRT reconstructs uniquely in .
Why The Precomputation Is Legit
The brute-force parts never touch the full range. They only verify small constant zones:
Everything above that is handled by CRT. That is the whole trick: make the scary range disappear behind a modulus product, and only brute-force the places where a query can still answer .
The solution is interactive, so every query and answer must be flushed, and if the interactor returns or says the final answer is wrong, the program exits immediately.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll digitSum(ll x, ll b) {
if (x < b) return -1;
ll s = 0;
while (x > 0) {
s += x % b;
x /= b;
}
return s;
}
int separatingBase(const vector<int>& xs) {
if (xs.size() <= 1) return 2;
int mx = *max_element(xs.begin(), xs.end());
for (int b = 2; b <= mx; ++b) {
set<ll> seen;
bool ok = true;
for (int x : xs) {
ll v = digitSum(x, b);
if (seen.count(v)) {
ok = false;
break;
}
seen.insert(v);
}
if (ok) return b;
}
return -1;
}
ll extgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll x1, y1;
ll g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return g;
}
ll modInv(ll a, ll mod) {
ll x, y;
ll g = extgcd(a, mod, x, y);
(void)g;
x %= mod;
if (x < 0) x += mod;
return x;
}
ll mergeCRT(ll r1, ll m1, ll r2, ll m2) {
ll t = (r2 - r1) % m2;
if (t < 0) t += m2;
t = t * modInv(m1 % m2, m2) % m2;
return r1 + m1 * t;
}
ll crt3(ll a36, ll a2000, ll a28587) {
ll r = a36 % 35, m = 35;
r = mergeCRT(r, m, a2000 % 1999, 1999);
m *= 1999;
r = mergeCRT(r, m, a28587 % 28586, 28586);
return r;
}
ll keyOf(ll a, ll b) {
return a * 100000LL + b;
}
ll ask(ll b) {
cout << '?' << ' ' << b << '\n' << flush;
ll a;
cin >> a;
if (a == -2) exit(0);
return a;
}
void answer(ll x) {
cout << '!' << ' ' << x << '\n' << flush;
int verdict;
cin >> verdict;
if (verdict != 1) exit(0);
}
int main() {
setIO();
int t, k;
ll c;
cin >> t >> k >> c;
map<ll, vector<int>> smallGroups;
for (int x = 1; x < 36; ++x) {
smallGroups[digitSum(x, 4)].push_back(x);
}
map<ll, int> smallChoice;
for (auto& [resp, xs] : smallGroups) {
smallChoice[resp] = separatingBase(xs);
}
map<ll, vector<int>> midGroups;
for (int x = 36; x < 2000; ++x) {
midGroups[digitSum(x, 36)].push_back(x);
}
map<ll, int> midChoice;
for (auto& [resp, xs] : midGroups) {
midChoice[resp] = separatingBase(xs);
}
map<ll, int> lowPair;
for (int x = 2000; x < 28587; ++x) {
ll a = digitSum(x, 36);
ll b = digitSum(x, 2000);
lowPair[keyOf(a, b)] = x;
}
while (t--) {
ll a36 = ask(36);
if (a36 == -1) {
ll a4 = ask(4);
int b = smallChoice[a4];
ll last = ask(b);
ll ans = -1;
for (int x = 1; x < 36; ++x) {
if (digitSum(x, 4) == a4 && digitSum(x, b) == last) {
ans = x;
break;
}
}
answer(ans);
continue;
}
ll a2000 = ask(2000);
if (a2000 == -1) {
int b = midChoice[a36];
ll last = ask(b);
ll ans = -1;
for (int x = 36; x < 2000; ++x) {
if (digitSum(x, 36) == a36 && digitSum(x, b) == last) {
ans = x;
break;
}
}
answer(ans);
continue;
}
ll a28587 = ask(28587);
ll ans;
if (a28587 == -1) {
ans = lowPair[keyOf(a36, a2000)];
} else {
ans = crt3(a36, a2000, a28587);
}
answer(ans);
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ll digitSum(ll x, ll b) {
if (x < b) return -1;
ll s = 0;
while (x > 0) {
s += x % b;
x /= b;
}
return s;
}
int separatingBase(const vector<int>& xs) {
if (xs.size() <= 1) return 2;
int mx = *max_element(xs.begin(), xs.end());
for (int b = 2; b <= mx; ++b) {
set<ll> seen;
bool ok = true;
for (int x : xs) {
ll v = digitSum(x, b);
if (seen.count(v)) {
ok = false;
break;
}
seen.insert(v);
}
if (ok) return b;
}
return -1;
}
ll extgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll x1, y1;
ll g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return g;
}
ll modInv(ll a, ll mod) {
ll x, y;
ll g = extgcd(a, mod, x, y);
(void)g;
x %= mod;
if (x < 0) x += mod;
return x;
}
ll mergeCRT(ll r1, ll m1, ll r2, ll m2) {
ll t = (r2 - r1) % m2;
if (t < 0) t += m2;
t = t * modInv(m1 % m2, m2) % m2;
return r1 + m1 * t;
}
ll crt3(ll a36, ll a2000, ll a28587) {
ll r = a36 % 35, m = 35;
r = mergeCRT(r, m, a2000 % 1999, 1999);
m *= 1999;
r = mergeCRT(r, m, a28587 % 28586, 28586);
return r;
}
ll keyOf(ll a, ll b) {
return a * 100000LL + b;
}
ll ask(ll b) {
cout << '?' << ' ' << b << '\n' << flush;
ll a;
cin >> a;
if (a == -2) exit(0);
return a;
}
void answer(ll x) {
cout << '!' << ' ' << x << '\n' << flush;
int verdict;
cin >> verdict;
if (verdict != 1) exit(0);
}
int main() {
setIO();
int t, k;
ll c;
cin >> t >> k >> c;
map<ll, vector<int>> smallGroups;
for (int x = 1; x < 36; ++x) {
smallGroups[digitSum(x, 4)].push_back(x);
}
map<ll, int> smallChoice;
for (auto& [resp, xs] : smallGroups) {
smallChoice[resp] = separatingBase(xs);
}
map<ll, vector<int>> midGroups;
for (int x = 36; x < 2000; ++x) {
midGroups[digitSum(x, 36)].push_back(x);
}
map<ll, int> midChoice;
for (auto& [resp, xs] : midGroups) {
midChoice[resp] = separatingBase(xs);
}
map<ll, int> lowPair;
for (int x = 2000; x < 28587; ++x) {
ll a = digitSum(x, 36);
ll b = digitSum(x, 2000);
lowPair[keyOf(a, b)] = x;
}
while (t--) {
ll a36 = ask(36);
if (a36 == -1) {
ll a4 = ask(4);
int b = smallChoice[a4];
ll last = ask(b);
ll ans = -1;
for (int x = 1; x < 36; ++x) {
if (digitSum(x, 4) == a4 && digitSum(x, b) == last) {
ans = x;
break;
}
}
answer(ans);
continue;
}
ll a2000 = ask(2000);
if (a2000 == -1) {
int b = midChoice[a36];
ll last = ask(b);
ll ans = -1;
for (int x = 36; x < 2000; ++x) {
if (digitSum(x, 36) == a36 && digitSum(x, b) == last) {
ans = x;
break;
}
}
answer(ans);
continue;
}
ll a28587 = ask(28587);
ll ans;
if (a28587 == -1) {
ans = lowPair[keyOf(a36, a2000)];
} else {
ans = crt3(a36, a2000, a28587);
}
answer(ans);
}
}