PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on a pile of N stones, alternating turns.
Alice can remove between 1 and A stones at a time.
Bob can remove between 1 and B stones at a time.
Who wins?
EXPLANATION:
We’ll do a bit of case analysis.
A > B
When A\gt B, Alice can always win.
Her strategy is quite simple:
- If there are \leq A stones remaining, remove them all.
- Otherwise, remove exactly 1 stone.
- Since A \gt B, removing exactly one stone when there are \gt A stones ensures that on Bob’s turn, there cannot be \leq B stones remaining.
So, Bob will never have a winning move, and Alice will eventually win.
- Since A \gt B, removing exactly one stone when there are \gt A stones ensures that on Bob’s turn, there cannot be \leq B stones remaining.
A < B
If N \leq A, Alice can of course win immediately by taking everything.
Otherwise, Alice can’t win immediately, and the turn passes to Bob.
Bob is now in the exact same situation as Alice was in, in case 1.
Using the exact same strategy (take everything if possible, otherwise take 1) allows Bob to win.
That is, in this case, Alice wins if N \leq A initially, and loses otherwise.
A = B
Both players have the same set of moves available now.
This situation is, in fact, a slight generalization of a rather well-known game — counting to 21.
The winning strategy is fairly simple if one tries to work backwards.
- If you want to win, you must have between 1 and A stones on your turn.
- The only way to force this, is to ensure that your opponent has A+1 stones on their previous turn.
- For that to happen, you must have had between A+2 and A+1+A stones on your previous turn.
- The only way to force that is if your opponent had exactly 2A+2 stones on their second-last turn.
\vdots
More generally, if you can ensure that on your opponent’s turn, the remaining number of stones is a multiple of (A+1), you’ll win.
So,
- If N is a multiple of A+1, Alice will lose, since whatever move she makes, Bob can bring it down to the next multiple of A+1.
- Otherwise, Alice wins - on her first move, she can bring N down to a multiple of A+1.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, a, b; cin >> n >> a >> b;
if (a > b){
cout << "Alice\n";
} else if (a < b){
if (n <= a) cout << "Alice\n";
else cout << "Bob\n";
} else {
if (n % (a + 1) == 0) cout << "Bob\n";
else cout << "Alice\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, a, b = map(int, input().split())
if a > b: print('Alice')
elif a < b:
if n <= a: print('Alice')
else: print('Bob')
else: print('Alice' if n%(a+1) != 0 else 'Bob')
