B. Lost Cursor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an optimization problem. The optimal solution for each test is not known to the jury, and your score for each test will be determined as described below.

The year is $$$6202$$$, and the world-famous artist Hcivelam is going through her retrospective phase. She has created a digital art piece that is hard for her contemporaries to explain, but it essentially looks like an ancient monochrome monitor. It is a play of space and negative space, a representation of the dual nature of everything: a grid of size $$$n \times n$$$ consisting of black and white pixels.

The piece is almost finished, but Hcivelam cannot complete it: she has lost her artistic tool, the cursor, somewhere on her black-and-white digital canvas. She does not know the cursor's position, but she knows for sure that it is currently located on a white pixel (if it were on a black pixel initially, she would already see it).

She can press the arrow keys on her keyboard to move the cursor: 'U' (up), 'D' (down), 'L' (left), and 'R' (right).

The cursor behaves as follows:

  • Movement: When you press a key, the cursor moves by one pixel in the corresponding direction.
  • Borders: If the cursor attempts to move outside the screen boundaries, it hits the edge and stays in its current position.
  • Visibility: If the cursor lands on a black pixel at any point, it immediately becomes visible, and you find it!

Your task is to help Hcivelam find a sequence of moves, as short as possible, such that regardless of where the cursor started, as long as it started on a white pixel, it is guaranteed to visit a black pixel at least once. The length of your sequence must not exceed $$$5000$$$.

Input

You are given a zip archive, "problem-b-inputs.zip", containing $$$8$$$ tests in the form of PNG images: 01.png, 02.png, $$$\ldots$$$, 08.png.

Each test describes the art-piece grid in standard grayscale PNG format. The size of the grid is $$$n \times n$$$ ($$$495 \le n \le 500$$$). Each pixel is either black or white, and there is at least one black pixel and at least one white pixel.

Output

Submit a zip archive with files 01.out, 02.out, $$$\ldots$$$, 08.out. Some of the files may be missing.

Each file should contain a single string consisting of the characters 'U', 'D', 'L', and 'R' — a sequence of moves that guarantees the cursor becomes visible.

Scoring

Your number of points is the length of the output string.

Your final score for the test is calculated as follows:

  • If the sequence of moves does not guarantee the cursor becomes visible, your score is $$$0$$$.
  • Otherwise, it will be $$$100$$$ times the square of the ratio of the lowest number of points among all participants for this test to the number of points for your output: $$$100 \cdot \left( \frac{\mathtt{best\_points}}{\mathtt{your\_points}} \right)^2$$$.

Note that the scoreboard will consider your best score for each test among all your submissions.

Note

We also provide two small sample grids in the zip archive "problem-b-samples.zip".

In the first sample, the grid is $$$2 \times 2$$$. In the explanations below, coordinates are given as $$$(\operatorname{row}, \operatorname{column})$$$.

The only black pixel is at $$$(2, 2)$$$. The cursor could be at $$$(1, 1)$$$, $$$(1, 2)$$$, or $$$(2, 1)$$$:

The sequence 'RD' guarantees that we find the cursor regardless of its starting position:

  • After moving 'R' (right):
    • $$$(1, 1) \to (1, 2)$$$
    • $$$(1, 2) \to (1, 2)$$$ (hits the border)
    • $$$(2, 1) \to (2, 2)$$$ (FOUND)
  • After moving 'D' (down):
    • $$$(1, 2) \to (2, 2)$$$ (FOUND)

Thus, one possible answer is: 

RD

In the second sample, the grid is $$$4 \times 4$$$:

One possible answer is: 

LLR

Note that the actual sample images have sizes $$$2 \times 2$$$ and $$$4 \times 4$$$, respectively. The larger illustrations above include thin lines between pixels for clarity only.

Problem by Recraft