問題一覧 > スコア問題

No.5006 Hidden Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 49
作問者 : platinum / テスター : butsurizuki
お気に入りにしたユーザー ProblemId : 8096 / 自分の提出
問題文最終更新日: 2022-06-11 22:58:16
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 score contest 1 (順位表) の他の問題:

Story

You are trying to investigate the internal structure of a certain building by remotely controlling a robot. Inside the building there are some walls that cannot be passed through.
If the robot tries to move in a direction where there is a wall, it tells you that there is a wall there and returns to the entrance.
Your goal is to discover a route from the entrance of the building to the exit.
However, this robot has a defect: it is known that, with a certain probability, it judges that there is a wall even when there is no wall in the direction of movement.

Problem Statement

You are given a grid with $\ 20\ $ rows and $\ 20\ $ columns. The outer boundary of the grid is a wall, and walls may also exist between adjacent cells.
The coordinates of the top-left cell are $(0, 0)$, and the coordinates of the cell reached by going $\ i\ $ cells down and $\ j\ $ cells right from there are $(i, j)$. The entrance of this building is located at cell $(0, 0)$, and the exit is located at cell $(19, 19)$.
A route that does not pass through a wall along the way and whose final position is the exit is called a "target route".
Repeat the following trial until you discover a target route. In each trial, the robot starts moving from the entrance.

  • Denoting moves up, down, left, and right by U, D, L, R respectively, output a movement route as a string of length at most $\ 400\ $.
  • If the output movement route is a target route, the judge returns $\ -1\ $. In that case, terminate the program immediately.
  • Otherwise, the number of moves the robot was able to make is returned. However, at each move, with a fixed probability $\ p\ $, the move fails and the trial ends even if there is no wall in the direction of movement.
  • In trial number $1001\ $, the judge returns $\ -1\ $, so terminate the program immediately.
Note that if a target route is output, the judge always returns $\ -1\ $.

Score

If you output a target route in trial number $t\ $, you get a score of $1001-t\ $. However, if the number of trials reaches $\ 1001\ $ or more, the score for that test case is $\ 0\ $.
If an output string contains characters other than U, D, L, R, the verdict is WA.
There are $\ 100\ $ test cases in total, and the sum of the scores of the test cases is the score of the submission.
The final ranking is determined by the highest score obtained during the contest, and no system test is performed after the contest ends.
The contest ranking can be viewed from the "Score Order" tab above.

Input

The input is given from standard input in the following format.

$H\ W\ p$

$H\ $ is the number of rows of the grid and $W\ $ is the number of columns of the grid, and $\ H=W=20\ $ holds in all test cases.
The probability $\ p\ $ that the robot fails to move is given as a percentage. $p\ $ is an integer between $\ 6\ $ and $\ 15\ $, inclusive.
It is guaranteed that all cells are reachable from the entrance.
Also, in each trial, after you output a string, one integer is given from standard input.
Be sure to read all of the judge's input to the end. If you do not, the verdict may be WA.

Output

In each trial, output one string of length at most $\ 400\ $. If the length of the output string exceeds $\ 400\ $, the characters from the $401\ $st onward are ignored.
Flush standard output after each output. Otherwise, the verdict may be TLE.
The behavior is undefined if the submitted program terminates before the judge returns $\ -1\ $, or if it produces output after the judge returns $\ -1\ $.

Sample

Sample 1
Input
5 5 10

In this sample the grid is made small for the sake of explanation, and it is not included in the actual test cases.
In this case, at each move, the robot fails to move with probability $\ 0.1\ $ even if there is no wall in the direction of movement.
Suppose the grid in this case is as shown in the figure below (it is not given in the input).

For example, the following trials are possible.

Output 1
DDDDRRRR
Input 1
2
Output 2
RRRRDDDD
Input 2
3
Output 3
RRRDDDDR
Input 3
-1

In trial number $1\ $, move number $3\ $ failed because there is a wall in the direction of movement, and $\ 2\ $ was returned.
In trial number $2\ $, move number $4\ $ failed due to the robot's defect even though there is no wall in the direction of movement, and $\ 3\ $ was returned.
In trial number $3\ $, a target route was output, so $\ -1\ $ was returned. In this test case, you get $\ 998\ $ points.

Input Generation

Let $\ rand(L,U)\ $ denote a function that generates an integer value between $L\ $ and $\ U\ $, inclusive, uniformly at random.
The probability that the robot fails to move in the $i\ $-th test case is $\ p=6+(i-1) \% 10\ $.
Also, although not given as input, the positions of the walls are determined by the following procedure.
First, let the total number of walls excluding the outer boundary be $\ M=rand(100,200)\ $, and repeat the following operation $\ M\ $ times.
However, if placing a wall would create an unreachable cell, or if a position where a wall has already been placed is chosen, the wall is not placed and the operation is redone.

  • Generate a random number $\ D=rand(0,1)\ $ that determines the direction of the wall.
  • If $D=0\ $, let $i=rand(0,19),j=rand(1,19)\ $ and place a wall between cell $\ (i,j-1)\ $ and cell $\ (i,j)\ $.
  • If $D=1\ $, let $i=rand(1,19),j=rand(0,19)\ $ and place a wall between cell $\ (i-1,j)\ $ and cell $\ (i,j)\ $.
For each test case, the maximum number of moves possible in each trial is determined in advance based on the probability $\ p\ $.
Repeat the following operation $\ 1000\ $ times to determine the numbers of possible moves $\ t\ $. The $\ i\ $-th operation is as follows.
  1. Generate an integer $\ c\ $ between $1\ $ and $\ 100\ $, inclusive, uniformly at random.
  2. If the number of times $c\ $ has been generated exceeds $\ 400 \ $, set $t_i=400\ $ and end the operation.
  3. If $c \leq p\ $, end the operation and set $t_i = (cを生成した回数) - 1\ $, where cを生成した回数 means the number of times c has been generated. Otherwise, return to step 1.
In trial number $i\ $, a move fails if there is a wall in the direction of movement or if it is an attempt to make move number $\ t_i+1\ $.

The test case generator and the judge program are available on GitHub.

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