We start by defining a winning position and a losing position. If the current player wins given optimal play on both sides, the position is a winning position, otherwise the position is a losing position.
For positions that are not immediately winning or losing positions, we can make the following two observations:
In the context of this problem, the pile having zero stones is a losing position, the pile having 1,2,…,9 stones is a winning position, and the pile having ten stones is a losing position.
Subtask 1: S<100.
We can naively check this process and compute for all S in increasing order if they are winning positions or losing positions.
T = int(input()) def is_pal(j): s = str(j) return s == "".join(reversed(s)) for _ in range(T): S = int(input()) win = [False] * (S+1) for i in range(S+1): for j in range(1, i+1): if is_pal(j) and not win[i-j]: win[i] = True print("B" if win[S] else "E")
Subtask 2: S<106.
This subtask rewarded people for experimenting with moves and only trying moves that involved taking at most 9 stones.
T = int(input()) S = 10**6 win = [False] * (S+1) for i in range(S+1): for j in range(1, min(i+1, 10)): if not win[i-j]: win[i] = True for _ in range(T): S = int(input()) print("B" if win[S] else "E")
Subtask 3: S<109.
If we look at the winning position and losing positions, we can see that a position is winning if and only if S is not divisible by 10. The proof of this follows directly from observing that taking anywhere from 1 to 9 stones is possible, but it is never possible to remove a multiple of ten. Therefore, we just naively check if the integer is divisible by 10.
Full Credit:
To check if a very large integer is a multiple of 10, it suffices to check if the last digit of the number is 0.
Benjamin Qi's code:
T = int(input()) for _ in range(T): start = input() print('E' if start[-1] == '0' else 'B')