分数: 600 点
问题陈述
考虑一个无限的二维坐标平面。 高桥最初站在 (0,0),可以 N 每次都会朝他选择的四个方向之一跳跃:上、下、左或右。 每次跳跃的长度是固定的。具体来说, i第次跳跃应覆盖的距离 D_i。 确定是否可以精确地位于 (A, B) 之后 N 跳跃。如果可能的话,请展示一种方法。
这里,对于每个方向,跳跃长度 D 来自 (X, Y) 让他得出以下观点:
- 向上: (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,在第二行打印所需的跳转序列作为字符串 S 长度 N 组成 U , D , L , R,如下:
- 如果 i第 次跳跃是向上的, i- 第一个字符应该是
U; - 如果 i第 次跳跃是向下的, i- 第一个字符应该是
D; - 如果 i第一个跳转是向左, i- 第一个字符应该是
L; - 如果 i- 第一个跳转是向右的, i- 第一个字符应该是
R.
示例输入 1
3 2 -2 1 2 3
示例输出 1
Yes LDR
如果他按照左、下、右的顺序跳,高桥就会移动 (0,0)\to(-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