#P3024. Cow Checkers
Cow Checkers
Cow Checkers
Bessie has challenged Farmer John to a game of Cow Checkers, played on an (M \times N) checkerboard. The board uses coordinates such that the bottom-left square is ((0, 0)) and the top-right square is ((M-1, N-1)). Initially, a single checker starts at position ((x, y)) with (0 \le x < M) and (0 \le y < N).
Players alternately move the checker with Bessie making the first move. In each turn, a player may make one of the following moves (provided the move keeps the checker on the board):
- Move the checker to any square on the same row to the left of its current position.
- Move the checker to any square on the same column below its current position.
- Move the checker diagonally: that is, move (k) squares to the left and (k) squares down concurrently, for any positive integer (k) such that the new position remains on the board.
The game ends when the current player is unable to make a move (i.e. when the checker is at ((0,0))). That player loses. Given the game is played for (T) rounds with a new starting position ((x,y)) provided for each round, determine the winner of each game assuming both players play optimally.
It can be shown that this game is equivalent to Wythoff Nim. In Wythoff Nim, a position ((x,y)) (assuming without loss of generality that (x \le y)) is a losing position if and only if (x = \lfloor (y - x)\phi \rfloor), where (\phi = \frac{1+\sqrt{5}}{2}) is the golden ratio. In such cases, the player whose turn it is (Bessie, if it is the first move) cannot force a win.
inputFormat
The first line of input contains three integers (M), (N) and (T) (the dimensions of the board and the number of games) separated by spaces. Each of the following (T) lines contains two integers (x) and (y) representing the starting position of the checker piece in that game.
outputFormat
For each game, output the winner's name on a new line: output either Bessie
if she can force a win or Farmer John
if she cannot.
sample
5 5 3
0 0
1 2
2 2
Farmer John
Farmer John
Bessie
</p>