No.2228 Creeping Ghost
タグ : / 解いたユーザー数 100
作問者 : 👑
akakimidori
Problem Statement
There is a grid with $5$ rows and $5$ columns as shown below. The cell in row $i$ and column $j$ is denoted by cell $(i,j)$. Initially, you are at cell $(1,1)$.
You will now make $T$ moves. In each move, you go to one of the cells adjacent up, down, left, or right (you cannot stay where you are). You also cannot move outside the grid.
Now, a ghost appears on this grid. At the same time as you make your $4k(k \geq 1)$-th move, the ghost moves to the destination cell of your $4(k-1)$-th move. (Here, the "destination cell of the $0$-th move" refers to cell $(1,1)$. The ghost does not appear until your $3$-rd move has been made.)
The ghost watches all cells in the same row or the same column as the cell it is in. Therefore, if you choose a cell satisfying either of the following conditions as a destination of your $4k(k \geq 1)$-th through $4k+3$-th moves, you will be found by the ghost.
- A cell in the same row as the destination cell of the $4(k-1)$-th move.
- A cell in the same column as the destination cell of the $4(k-1)$-th move.
Find one way to make $T$ moves without being found by the ghost. It can be shown that such a way of moving exists under the constraints of this problem.
What up, down, left, and right mean (click to expand)
The directions of moves to adjacent cells are defined as follows.
- Move to the upper cell: a move from cell $(i,j)$ to cell $(i-1,j)$.
- Move to the lower cell: a move from cell $(i,j)$ to cell $(i+1,j)$.
- Move to the left cell: a move from cell $(i,j)$ to cell $(i,j-1)$.
- Move to the right cell: a move from cell $(i,j)$ to cell $(i,j+1)$.
Constraints
- $T$ is an integer.
- $1 \leq T \leq 10^6$
Input
The input is given from standard input in the following format.
$T$
Output
Output a way to make $T$ moves without being found by the ghost, as a string $S$ of length $T$ consisting of L,R,U,D.
Here, the $i$-th character of $S$ being L,R,U,D means that the direction of the $i$-th move is left, right, up, down, respectively.
If there are multiple ways of moving that satisfy the conditions, any of them will be accepted.
Sample
Sample 1
Input
9
Output
RDRDRURUL
The movement is shown below. The red circles represent your destination cells, the red stars represent the cells where the ghost is, and the cells filled in blue represent the range of cells where you would be found by the ghost.
With this way of moving, you can move to the end without being found by the ghost, so this way of moving is one of the correct answers. Note that after the $8$-th move, the ghost has moved to cell $(3,3)$, the cell you reached after the $4$-th move, so you are not found by the ghost at the destination cell $(1,5)$.
On the other hand, if you move as RDRDRURDU, for example, you will be found by the ghost after the $8$-th move as shown in the figure below, so this way of moving is incorrect.
Sample 2
Input
3
Output
DRU
Since the ghost does not appear until the $3$-rd move, any way of moving is accepted as long as you do not go outside the grid.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。