102216: [AtCoder]ABC221 G - Jumping sequence

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

Consider an infinite two-dimensional coordinate plane. Takahashi, who is initially standing at $(0,0)$, will do $N$ jumps in one of the four directions he chooses every time: up, down, left, or right. The length of each jump is fixed. Specifically, the $i$-th jump should cover the distance of $D_i$. Determine whether it is possible to be exactly at $(A, B)$ after $N$ jumps. If it is possible, show one way to do so.

Here, for each direction, a jump of length $D$ from $(X, Y)$ takes him to the following point:

  • up: $(X,Y) \to (X,Y+D)$
  • down: $(X,Y) \to (X,Y-D)$
  • left: $(X,Y) \to (X-D,Y)$
  • right: $(X,Y) \to (X+D,Y)$.

Constraints

  • $1 \leq N \leq 2000$
  • $\lvert A\rvert, \lvert B\rvert \leq 3.6\times 10^6$
  • $1 \leq D_i \leq 1800$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $A$ $B$
$D_1$ $D_2$ $\ldots$ $D_N$

Output

In the first line, print Yes if there is a desired sequence of jumps, and No otherwise.
In the case of Yes, print in the second line a desired sequence of jumps as a string $S$ of length $N$ consisting of U , D , L , R, as follows:

  • if the $i$-th jump is upward, the $i$-th character should be U;
  • if the $i$-th jump is downward, the $i$-th character should be D;
  • if the $i$-th jump is to the left, the $i$-th character should be L;
  • if the $i$-th jump is to the right, the $i$-th character should be R.

Sample Input 1

3 2 -2
1 2 3

Sample Output 1

Yes
LDR

If he jumps left, down, right in this order, Takahashi moves $(0,0)\to(-1,0)\to(-1,-2)\to(2,-2)$ and ends up at $(2, -2)$, which is desired.


Sample Input 2

2 1 0
1 6

Sample Output 2

No

It is impossible to be exactly at $(1, 0)$ after the two jumps.


Sample Input 3

5 6 7
1 3 5 7 9

Sample Output 3

Yes
LRLUR

Input

题意翻译

有一个无限大的平面直角坐标系,初始时你在 $(0,0)$ 处。给你一个长度为 $n$ 的序列 $d$,你可以移动 $n$ 步,每一步可以选择: - 向上移动 $d_i$ 距离,从 $(x,y)$ 到 $(x,y+d_i)$ - 向下移动 $d_i$ 距离,从 $(x,y)$ 到 $(x,y-d_i)$ - 向右移动 $d_i$ 距离,从 $(x,y)$ 到 $(x+d_i,y)$ - 向左移动 $d_i$ 距离,从 $(x,y)$ 到 $(x-d_i,y)$ 你想在 $n$ 步结束后位于 $(A,B)$ 位置,问是否存在这样的方案,如果存在需输出任意一种方案。

Output

分数:$600$分

问题描述

考虑一个无限的二维坐标平面上。Takahashi 初始站在点 $(0,0)$,他将进行 $N$ 次跳跃,每次他可以选择四个方向之一:上、下、左、右。每次跳跃的长度是固定的。具体来说,第 $i$ 次跳跃应该覆盖 $D_i$ 的距离。确定是否可能在 $N$ 次跳跃后正好到达 $(A, B)$。如果可能,请给出一种跳跃的方法。

在这里,对于每个方向,从 $(X, Y)$ 的长度为 $D$ 的跳跃将他带到以下点:

  • 上:$(X,Y) \to (X,Y+D)$
  • 下:$(X,Y) \to (X,Y-D)$
  • 左:$(X,Y) \to (X-D,Y)$
  • 右:$(X,Y) \to (X+D,Y)$。

约束

  • $1 \leq N \leq 2000$
  • $\lvert A\rvert, \lvert B\rvert \leq 3.6\times 10^6$
  • $1 \leq D_i \leq 1800$
  • 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出:

$N$ $A$ $B$
$D_1$ $D_2$ $\ldots$ $D_N$

输出

在第一行中,如果存在所需的跳跃序列,则打印 Yes,否则打印 No
Yes 的情况下,在第二行中打印一个所需的跳跃序列,作为长度为 $N$ 的字符串 $S$,由 UDLR 组成,如下所示:

  • 如果第 $i$ 次跳跃是向上的,则第 $i$ 个字符应该是 U
  • 如果第 $i$ 次跳跃是向下的,则第 $i$ 个字符应该是 D
  • 如果第 $i$ 次跳跃是向左的,则第 $i$ 个字符应该是 L
  • 如果第 $i$ 次跳跃是向右的,则第 $i$ 个字符应该是 R

样例输入 1

3 2 -2
1 2 3

样例输出 1

Yes
LDR

如果他按照 LDR 的顺序跳跃,Takahashi 将从 $(0,0)$ 移动到 $(-1,0)\to(-1,-2)\to(2,-2)$,最后到达 $(2, -2)$,这是所需的。


样例输入 2

2 1 0
1 6

样例输出 2

No

在两次跳跃后,不可能正好到达 $(1, 0)$。


样例输入 3

5 6 7
1 3 5 7 9

样例输出 3

Yes
LRLUR

加入题单

上一题 下一题 算法标签: