# YETALICEBOB - Editorial

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

TBD

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.
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

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')

1 Like

public static void solve()throws IOException{
long n=ip.nextInt(), a=ip.nextInt(), b=ip.nextInt();

	if(n<=a){
System.out.println("Alice");
}else{
if(a>b)System.out.println("Alice");
else if(b<a)System.out.println("Bob");
else{
if(n%(a+1)==0)System.out.println("Bob");
else System.out.println("Alice");
}
}

}


anyone help me find issue in this

one small mistake that the condition in the if and else if are same

What would be the answer in a generalized case where A = B and the minimum coins that can be picked are not necessarily 1?

Actually I want to know if both players could pick min X and max Y coins in their turn with Alice going first, then would the answer simply be:

if(n%(X+Y) == 0) cout<<"Bob";
else cout<<"Alice";


In that case, the answer still depends on the relation between N and X+Y, but it’s not quite as simple as checking for multiples.
For a simple example, if X = 10, Y = 20 and N = 5, even though N is not a multiple of X+Y, Alice can’t win (since it’s not even possible to make a move).

It’s not hard to come up with a condition though.

Hint

Try extending the situation in my example above to other cases where Alice can’t win.

AtCoder ABC 297G is one problem that has this generalization (but you’ll need to know a bit more game theory to actually solve it).

1 Like