B - AB Game Editorial by evima
[1] When does Alice win?
Let \(n\) be the initial number of stones and analyze the relation between \(n\), \(A\), and \(B\) when Alice wins.
If \(n<A\), Alice loses. Below, assume \(n\geq A\).
Here is an important fact that we need to notice:
- it is optimal for Alice to take as many stones as possible.
Proof
When $A\leq B$, Alice can win by taking as many stones as possible to leave less than $A$ stones, so the statement holds. When $A>B$, it follows from the argument above that Bob will win if Alice leaves $A$ or more stones in her first turn, so again Alice should take as many stones as possible.Therefore, the necessary and sufficient condition for Alice’s win is:
- \(n\geq A\) and \(n\bmod A <B\).
[2] Computing the count
Let us count the integers \(n\) that satisfy the condition above.
Let \(f(X)\) be the number of \(n\)’s such that \(n\bmod A<B\) and \(1 \leq n \leq X\).
The answer is the number of \(n\)’s between \(A\) and \(N\) satisfying \(n\bmod A<B\), so it can be represented as \(f(N) - f(A-1)\).
Using the fact that \(X \bmod A\) is in a cyclic pattern \(1,2,\ldots,A-1, 0,1,2,\ldots\), we can compute \(f(X)\) by the following formula:
\[ f(X)=\lfloor \frac{N}{A}\rfloor \mathrm{min}(A, B) +\mathrm{min}(N \bmod A, B-1).\]
This can be done in \(O(1)\) time, so the problem is solved in \(O(1)\) time.
[3] Sample Implementation
Python:
n, a, b = map(int, input().split())
def f(x):
return x // a * min(a, b) + min(x % a, b - 1)
print(max(f(n) - f(a - 1), 0))
posted:
last update: