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
to any of these points: , , and . -
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
If the player fails to catch the mouse within
Interaction
In each round:
-
First, your program writes an integer
— the number of steps you want the cat to move, followed by a space and characters, each must be one of ‘LRUD’, representing the direction you want the cat to move. -
Your program then reads an integer
— the squared Euclidean distance between the cat and the mouse. If , you win and your program should terminate immediately.
Initially, the squared Euclidean distance between the cat
and the mouse is at most
Communication example
In this example, the cat is initially at
|
|
|
|||||
|
|
||||||
|
|
||||||
|
|
||||||
|
|
||||||
|
|
||||||
|
|
||||||
|
|
||||||
|
|
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().