Problem D
Cutting Brownies
John Horton Conway (1937-) is a British mathematician with many contributions to mathematics. He is famous for the invention of the cellular automaton, more popularly known as the “Game of Life.” This problem is inspired by a game Conway invented in the 1970s.
This game is played using a rectangular sheet of brownies fresh out of the oven. The players are Harry Horizontal and Vicky Vertical. Initially, there is a single piece consisting of $B \times D$ connected squares (the individual brownies).
At each turn, a player chooses one of the remaining pieces and if possible, cuts it into two smaller pieces such that both pieces have integer breadth and depth. Harry may make only horizontal cuts, Vicky only vertical cuts. Pieces may not be rotated before or after a cut. If a player cannot cut any of the remaining pieces, that player loses.
Let’s consider some examples. The simplest game is . In this case, neither Harry nor Vicky can make a move, so whoever starts loses. On the other hand, is a win for Harry, no matter who starts. Similarly, is a win for Vicky, no matter who starts.
Consider , which is a loss for whoever starts. For instance, if Vicky starts, her only move leaves Harry with , and once he cuts any of the pieces, Vicky is left with , , (in any order) and thus again without moves. For reasons of symmetry, Harry loses if he is made to start.
Intuition might tell us that Vicky should tend to win if the initial sheet is broader than it is deep (since such sheets yield more opportunities for vertical cuts), but consider . If Harry starts, his only possible move leaves Vicky with , and a win. But if Vicky starts, any possible move leaves Harry with , . Harry responds and leaves Vicky with , , , which Vicky will eventually lose since there are no moves left in the $2$ sheets and whoever makes the first move on loses.
On the other hand, is a winner for Vicky, no matter who starts. If Harry starts, he runs out of moves after his first cut. If Vicky starts, her best move is to cut in the center, leaving Harry with , , which he loses because each game is lost by whoever moves first.
Given the initial size of the sheet, and given who starts the game, write a program that computes if the starting player has a strategy to force a win!
Input
The first line contains an integer $1 \le N \le 10$ denoting the number of test cases that follow. Each test case consists of a single line containing two integers $B$ and $D$, and a string $S$. Here $B$ denotes the initial breadth of the sheet ($1 \le B \le 500$), $D$ denotes the initial depth of the sheet ($1 \le D \le 500$) and $S$ is either Harry or Vicky depending on whether Harry or Vicky moves first.
Output
For each test case, output whether the player who starts can force a win in the game. Output the player’s name followed by can win or cannot win.
Sample Input 1 | Sample Output 1 |
---|---|
5 1 1 Harry 2 2 Vicky 3 2 Vicky 4 2 Vicky 6 8 Harry |
Harry cannot win Vicky cannot win Vicky cannot win Vicky can win Harry can win |