Knight Game
Time limit2sMemory limit1024 MB
Given a knight on an H by W board, decide whether Alice or Bob wins when both alternately move the knight to unvisited squares.
- Level
Hard8 of 10
- Topics
- Game theory, Graph, Math
- Solved
- No attempts yet
Problem
The rule of this game is given as follows.
- There is a knight and a chessboard with rows and columns. The square at the -th row from the top and the -th column from the left is called square . Initially, the knight is placed on square .
- Alice and Bob take turns, starting with Alice. On each turn, the player moves the knight to one of the unvisited squares according to the knight's movement rule.
- The knight can move from to if and only if is .
- The player who cannot move the knight loses.
Assuming both players play optimally, determine whether Alice or Bob wins. Answer for test cases.
An unvisited square is defined as follows.
- A square on the board that the knight has never visited since the start of the game.
Input
is the -th test case.
Each test case is given in the following format.
Output
Output lines. On line , print the winner of the -th test case, Alice or Bob.
Constraints
- All inputs are integers.