No.1315 Spiral Cave
タグ : / 解いたユーザー数 28
作問者 :
りあん
/ テスター :
tempura_pp
Problem Statement
Consider an infinite two-dimensional grid as shown in the figure below. The cells are numbered in a counterclockwise spiral centered at cell $1$.
Starting from cell $S$, you travel to cell $T$ by repeatedly moving to one of the cells adjacent up, down, left, or right.
The bitwise exclusive OR (Exclusive or - Wikipedia) of the numbers of the cells you pass through (including $S, T$) is calculated as the penalty (a cell visited multiple times is counted as many times as it is visited).
More precisely, if the numbers of the cells you pass through are, in order, $C_0 (= S), C_1, C_2, \ \ldots \ , C_{K-1}, C_K (= T)$, the penalty is calculated as $C_0 \oplus C_1 \oplus C_2 \oplus \cdots \oplus C_{K-1} \oplus C_K$.
Find one way of moving from cell $S$ to cell $T$ that satisfies both of the following 2 conditions.
- Its penalty is the minimum among all ways of moving from cell $S$ to cell $T$
- The number of steps (the number of moves to a cell adjacent up, down, left, or right) is at most $2 \times 10^5$
If multiple ways satisfy the conditions, you may output any of them (note that you do not need to minimize the number of steps).
It can be proved that, under the constraints of this problem, a way satisfying both of the 2 conditions always exists (among the moves with the minimum penalty, there is always one with at most $2 \times 10^5$ steps).
Input
$S$ $T$
An integer $S$ representing the number of the starting cell and an integer $T$ representing the number of the goal cell are given on one line, separated by a single space.
The input satisfies the following constraints.
- All input values are integers
- $1 \le S, T \le 10^9$
- $S \neq T$
Output
$X$ $K$ $D_1 D_2 \ldots D_K$
The expected output consists of 3 lines.
On the first line, output the minimum penalty $X$ as an integer.
On the second line, output the number of steps (the number of moves to a cell adjacent up, down, left, or right) $K$ as an integer. It must satisfy $1 \le K \le 2 \times 10^5$.
On the third line, output a string $D$ representing the way of moving. The string $D$ must satisfy all of the following conditions.
- $D$ is a string of length $K$
- $D$ consists only of
L,R,U,D - Letting $C_i$ be the number of the cell you are at after repeating the move to an adjacent cell $i \ (0 \le i \le K)$ times, all of the following conditions hold
- $C_0 = S$
- $C_K = T$
- For every integer $i$ satisfying $1 \le i \le K$,
- if $D_i =$
L, then $C_i$ is the cell adjacent to the left of $C_{i-1}$ - if $D_i =$
R, then $C_i$ is the cell adjacent to the right of $C_{i-1}$ - if $D_i =$
U, then $C_i$ is the cell adjacent above $C_{i-1}$ - if $D_i =$
D, then $C_i$ is the cell adjacent below $C_{i-1}$
- if $D_i =$
- $C_0 \oplus C_1 \oplus \cdots \oplus C_K = X$
If there are multiple solutions, you may output any of them.
Sample
Sample 1
Input
3 13
Output
0 2 UR
By going from cell $3$ through cell $14$, which is adjacent above it, to cell $13$, the penalty becomes $ \ 3 \oplus 14 \oplus 13 = 0 \ $.
Sample 2
Input
23 16
Output
0 7 LLUURUU
Sample 3
Input
4 8
Output
0 8 DDLDDRUU
It is also allowed to pass through $T$ along the way or to pass through the same cell two or more times.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。