409202: GYM103456 E Ppopgi

The remaining contestants hear that they must play ppopgi but the game has a new twist. Rather than having a contestant extract a stamped shape from the honeycomb, they must instead play the following game:

Each player is randomly paired with another player. They are given a large, rectangular honeycomb with a length of $$$x$$$ centimeters and width $$$y$$$ centimeters. Then, the players must alternate cutting circles of radius $$$r$$$ centimeters out from the rectangle where the new circle being cut out must be whole (i.e. you cannot cut a circle that overlaps - though it is allowed to be tangential to - another already cut-out circle or does not fit within the rectangle). Each player may choose any part of the rectangle to cut the circle out of as long as they can still cut out a circle of radius $$$r$$$ centimeters as described above. A player loses when they are no longer able to cut out a circle of the desired size.

Players 067 and 199 are drawn to play against each other with player 199 getting to go first. Given that both players' lives are on the line, they both play optimally. Player 001 is watching from the outside and wants you to figure out who will win the game.

The input is three space-separated integers $$$x, y, r$$$ where $$$x$$$ and $$$y$$$ are the length and width of the honeycomb in centimeters and $$$r$$$ is the radius of the desired circle in centimeters ($$$1 \leq x, y, r \leq 1000$$$).

Output the ID of the player who wins if both play optimally and player 199 goes first (output 199 if player 199 wins and 067 if player 067 wins).

7 7 3

199

6 5 4

067

In the first test case, there is only room to cut out one circle so player 199 wins.