Problem F
Fluffy Cat
You are working on your new mobile game Fluffy Cat. With simple yet engaging game play, it will surely become a top mobile game!
In this game, a single player controls a cat in an infinite grid. There is a mouse hidden somewhere in this grid. To win the game, the player must catch the mouse. The game consists of several rounds. In each round:
-
The player moves the cat at most two (possibly zero) steps. In each step, the cat can move one unit of length towards any of the following directions: up, down, left and right. More precisely, in one step, the cat can move from the current point $(x, y)$ to any of these $4$ points: $(x - 1, y)$, $(x + 1, y)$, $(x, y - 1)$ and $(x, y + 1)$.
-
If the cat and the mouse are at the same point, the mouse must not move, the game ends immediately and the player wins.
-
Otherwise, the mouse moves exactly one unit of length towards any of the directions up, down, left and right. The mouse moves using a pre-written algorithm which is hidden from the player.
-
If the cat and the mouse are at the same point, the game ends immediately and the player wins. Otherwise, the game continues to the next round.
At the end of each round, the player is informed the squared Euclidean distance between the cat and the mouse. If this distance equals to $0$, the game has ended and the player has already won. If the cat is at point $(x_ c ,y_ c)$ and the mouse is at point $(x_ m, y_ m)$, then the squared Euclidean distance between the cat and the mouse is defined as: $(x_ c - x_ m)^2 + (y_ c - y_ m)^2$.
If the player fails to catch the mouse within $10\, 000$ rounds, he loses the game. Your task is to win the game no matter how the mouse plays.
Interaction
In each round:
-
First, your program writes an integer $k$ $(0 \le k \le 2)$ — the number of steps you want the cat to move, followed by a space and $k$ characters, each must be one of ‘LRUD’, representing the direction you want the cat to move.
-
Your program then reads an integer $d$ — the squared Euclidean distance between the cat and the mouse. If $d = 0$, you win and your program should terminate immediately.
Initially, the squared Euclidean distance between the cat and the mouse is at most $10^6$. The cat must catch the mouse within $10\, 000$ rounds.
Communication example
In this example, the cat is initially at $(0, 0)$, the mouse is at $(1, 0)$. The mouse is programmed to always move right (from $(x, y)$ to $(x + 1, y)$). Note that your program knows neither the initial positions nor the strategy of the mouse. Also, this strategy is not used in our interactor.
|
|
|
|||||
|
$2$ RL |
|
||||||
|
$4$ |
|
||||||
|
$2$ RU |
|
||||||
|
$5$ |
|
||||||
|
$2$ RR |
|
||||||
|
$2$ |
|
||||||
|
$2$ RD |
|
||||||
|
$0$ |
|
Notes
In this problem, the interactor is adaptive — the jury program can move the mouse using different strategies, depending on your program’s output.
When you write the solution for the interactive problem it is important to keep in mind that if you output some data it is possible that this data is first placed to some internal buffer and may be not directly transferred to the interactor. In order to avoid such situation you have to use special ‘flush’ operation each time you output some data. There are these ‘flush’ operations in standard libraries of almost all languages. For example, in C++ you may use fflush(stdout) or cout << flush (it depends on what do you use for output data — scanf/printf or cout). In Java you can use method ‘flush’ for output stream, for example, System.out.flush(). In Python you can use stdout.flush().
