問題一覧 > 通常問題

No.3069 Invisible Speedrun

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 108
作問者 : 👑 AngrySadEight / テスター : 👑 seekworser 👑 hamamu
お気に入りにしたユーザー ProblemId : 11937 / 自分の提出
問題文最終更新日: 2025-03-19 21:17:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 461 (順位表) の他の問題:

Problem Statement

This is an interactive problem (a problem in which your program and the judge program interact via standard input and output).


There is a grid with $N$ rows and $N$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by cell $(i, j)$.

Among the cells of this grid other than cell $(1, 1)$ and cell $(N, N)$, $1$ cell has a wall placed on it. The cell with the wall is not given in the input.

$1$ robot is at cell $(1, 1)$. Your goal is to move this robot to cell $(N, N)$ by using the following $4$ types of commands.

  • Command Down: Let cell $(i, j)$ be the current cell. If cell $(i + 1, j)$ exists and has no wall, move to cell $(i + 1, j)$. Otherwise, stay at cell $(i, j)$.
  • Command Right: Let cell $(i, j)$ be the current cell. If cell $(i, j + 1)$ exists and has no wall, move to cell $(i, j + 1)$. Otherwise, stay at cell $(i, j)$.
  • Command Up: Let cell $(i, j)$ be the current cell. If cell $(i - 1, j)$ exists and has no wall, move to cell $(i - 1, j)$. Otherwise, stay at cell $(i, j)$.
  • Command Left: Let cell $(i, j)$ be the current cell. If cell $(i, j - 1)$ exists and has no wall, move to cell $(i, j - 1)$. Otherwise, stay at cell $(i, j)$.

However, the grid is very dark, and you cannot tell whether the robot moved as a result of using a command.

Reach cell $(N, N)$ using at most $2N$ commands.

The cell with the wall is determined before the interaction between your program and the judge system.

Constraints

  • $N$ is an integer
  • $2 \leq N \leq 1000$
  • The cell with the wall is neither cell $(1, 1)$ nor cell $(N, N)$

Input and Output

This is an interactive problem (a problem in which your program and the judge program interact via standard input and output).

First, $N$ is given from standard input.

$N$

Then, you may use commands at most $2N$ times.

To use a command, output in the following format, where $d$ is the type of the command. Here, the characters representing the Down, Right, Up, and Left commands are D, R, U, and L, respectively.

$d$

After each use of a command, a value representing the result is given from standard input in the following format.

$v$

Here, $v$ is an integer, where:

  • $v = 0$ means that the robot has not yet reached cell $(N, N)$.
  • $v = 1$ means that the robot has reached cell $(N, N)$. After receiving this input, terminate your program immediately.
  • $v = -1$ means that you made an output violating the constraints, or that the number of commands used has exceeded $2N$. In this case, your program has already been judged as incorrect, so terminate your program immediately.

In particular, note that neither the cell where the robot is nor whether the robot has moved is given in the input.

Notes

  • Be sure to flush standard output after every output. Otherwise, you may get TLE.
  • If an invalid output is made, the judge result is undefined.
  • If your program does not terminate immediately after $v = -1$ is given as input, the judge result is undefined.
  • Terminate your program immediately after $v = 1$ is given as input. Otherwise, the judge result is undefined.
If you are not familiar with reactive problems, please also see the summary of reactive-format problems.

Sample

The following is an example of a correct interaction for the case where $N = 3$ and the cell with the wall is $(2, 3)$.

InputOutputExplanation
3 $N = 3$.
D Use Command Down. Cell $(2, 1)$ exists and has no wall, so the robot moves to cell $(2, 1)$.
0 Cell $(3, 3)$ has not been reached yet.
D Use Command Down. Cell $(3, 1)$ exists and has no wall, so the robot moves to cell $(3, 1)$.
0 Cell $(3, 3)$ has not been reached yet.
R Use Command Right. Cell $(3, 2)$ exists and has no wall, so the robot moves to cell $(3, 2)$.
0 Cell $(3, 3)$ has not been reached yet.
R Use Command Right. Cell $(3, 3)$ exists and has no wall, so the robot moves to cell $(3, 3)$.
1 Cell $(3, 3)$ has been reached. Therefore, terminate your program here.

An example of an incorrect interaction for the case where $N = 3$ and the cell with the wall is $(2, 3)$ is also shown.

InputOutputExplanation
3 $N = 3$.
R Use Command Right. Cell $(1, 2)$ exists and has no wall, so the robot moves to cell $(1, 2)$.
0 Cell $(3, 3)$ has not been reached yet.
R Use Command Right. Cell $(1, 3)$ exists and has no wall, so the robot moves to cell $(1, 3)$.
0 Cell $(3, 3)$ has not been reached yet.
R Use Command Right. Cell $(1, 4)$ does not exist, so the robot stays at cell $(1, 3)$.
0 Cell $(3, 3)$ has not been reached yet.
D Use Command Down. Cell $(2, 3)$ exists but has a wall, so the robot stays at cell $(1, 3)$.
0 Cell $(3, 3)$ has not been reached yet.
L Use Command Left. Cell $(1, 2)$ exists and has no wall, so the robot moves to cell $(1, 2)$.
0 Cell $(3, 3)$ has not been reached yet.
D Use Command Down. Cell $(2, 2)$ exists and has no wall, so the robot moves to cell $(2, 2)$.
0 Cell $(3, 3)$ has not been reached yet.
D Use Command Down. Cell $(3, 2)$ exists and has no wall, so the robot moves to cell $(3, 2)$.
-1 The number of commands used exceeded $2N$, so $v = -1$ was given as input. At this point, your program has already been judged as incorrect, so terminate your program.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。