← 返回题目列表

AtCoder · abc221_g

G. 跳跃顺序

中文机器翻译题面 查看原题

分数: 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