P10737 [SEERC 2020] Reverse Game

Alice and Bob are playing a game with the following rules: - Before the game starts, a string $s$ is given. - In each move, choose a substring $t$ of $s$. The substring $t$ must be one of `10`, `100`, `110`, `1010`. Then flip every character in $t$. For example, flipping `100` becomes `001`. - The player who cannot make a move loses the game. Alice moves first. Assuming both players use optimal strategies, determine who will win.

A string $s$ containing only $0$ and $1$ $(1 \leq |s| \leq 10^6)$.

If Alice wins, output `Alice`. If Bob wins, output `Bob`.

For sample $1$, after choosing the substring `10` and flipping it, Bob cannot make a move. Translated by ChatGPT 5