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.
This is still just ordinary Nim. The dumpers are the piles, so the winner is determined entirely by the xor of all pile sizes. No fancy game theory twist hiding under the bed.
You obviously cannot iterate through all dumpers: one quarry alone may have of them. So for each quarry, you need to compute in .
Introduce a prefix-xor function Then the xor of any consecutive range is So now the whole problem is: how do you compute fast?
Write out the first few values: The pattern repeats every :
t,& t\bmod 4=0\\ 1,& t\bmod 4=1\\ t+1,& t\bmod 4=2\\ 0,& t\bmod 4=3 \end{cases}$$ That’s the magic trick. Old but deadly.For each quarry, let and . Its contribution to the total nim-sum is
Then compute
If , the first player wins, so print tolik; otherwise print bolik. Total complexity: time and extra memory.
Strip away the industrial flavor text, and this is just Nim. Every dumper is a pile whose size is the number of stones in it.
So by Bouton’s theorem:
So the answer is determined by
If , print tolik, else print bolik.
The only real problem is computing those huge consecutive xors without doing something stupid like iterating times. That would be... ambitious.
Define
Then for any ,
Why? Because everything from to appears twice and cancels in xor.
So quarry contributes
Now we just need in .
This is the classic xor-prefix pattern. Compute a few values:
The answer depends only on :
One way to remember it: xor over every full block of four numbers vanishes:
So only the leftover tail matters.
For each quarry:
At the end:
tolik;bolik.We can package the proof into three tiny lemmas.
A Nim position is losing iff the xor of all pile sizes is .
This is the standard theorem for normal-play Nim.
For any ,
Proof.
Xor this with
and the common prefix cancels. Done.
For every ,
Proof. Check the first four values, then note the pattern repeats because each block of four consecutive integers xors to .
From Lemma 2 and Lemma 3, each quarry’s contribution is computed correctly in . From Lemma 1, the final xor decides the winner. So the algorithm is correct.
For each of the quarries we do only constant work.
That’s it. The whole problem is basically “remember the xor-prefix formula and don’t panic because the numbers look huge.”
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ull prefXor(ull x) {
switch (x & 3ULL) {
case 0: return x;
case 1: return 1;
case 2: return x + 1;
default: return 0;
}
}
int main() {
setIO();
int n;
cin >> n;
ull nim = 0;
for (int i = 0; i < n; ++i) {
ull x, m;
cin >> x >> m;
ull l = x;
ull r = x + m - 1;
nim ^= prefXor(r) ^ prefXor(l - 1);
}
cout << (nim ? "tolik" : "bolik") << '\n';
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
ull prefXor(ull x) {
switch (x & 3ULL) {
case 0: return x;
case 1: return 1;
case 2: return x + 1;
default: return 0;
}
}
int main() {
setIO();
int n;
cin >> n;
ull nim = 0;
for (int i = 0; i < n; ++i) {
ull x, m;
cin >> x >> m;
ull l = x;
ull r = x + m - 1;
nim ^= prefXor(r) ^ prefXor(l - 1);
}
cout << (nim ? "tolik" : "bolik") << '\n';
return 0;
}