P2953 [USACO09OPEN] Cow Digit Game S

Bessie is playing a number game against Farmer John, and she wants you to help her win. Game $i$ starts with an integer $N_i$ ($1 \le N_i \le 1{,}000{,}000$). Bessie goes first, and then the two players alternate turns. On each turn, a player can subtract from the current number either its largest digit or its smallest nonzero digit to obtain a new number. For example, from $3014$ we may subtract either $1$ or $4$ to obtain either $3013$ or $3010$, respectively. The game continues until the number becomes $0$, at which point the last player to have taken a turn is the winner. Bessie and FJ play $G$ ($1 \le G \le 100$) games. Determine, for each game, whether Bessie or FJ will win, assuming both play optimally (that is, on each turn, if the current player has a move that guarantees a win, they will take it). Consider a sample game where $N_i = 13$. Bessie goes first and takes $3$, leaving $10$. FJ is forced to take $1$, leaving $9$. Bessie takes the remainder and wins the game.

* Line 1: A single integer $G$. * Lines 2..$G+1$: Line $i+1$ contains the single integer $N_i$.

* Lines 1..$G$: Line $i$ contains 'YES' if Bessie can win game $i$, and 'NO' otherwise.

For the first game, Bessie simply takes the number $9$ and wins. For the second game, Bessie must take $1$ (since she cannot take $0$), and then FJ can win by taking $9$. Translated by ChatGPT 5