AT_abc221_g [ABC221G] Jumping sequence

题目描述

考虑一个无限扩展的二维坐标平面。高桥君最初站在 $(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)$

输入格式

输入从标准输入读入，格式如下：

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

输出格式

如果存在满足条件的移动方案，则在第 $1$ 行输出 Yes，否则输出 No。
如果输出 Yes，则在第 $2$ 行输出一个由 U、D、L、R 组成的长度为 $N$ 的字符串 $S$，表示一种满足条件的移动方案。
其中，$S$ 的第 $i$ 个字符含义如下：

• U：第 $i$ 次跳跃向上
• D：第 $i$ 次跳跃向下
• L：第 $i$ 次跳跃向左
• R：第 $i$ 次跳跃向右

输入输出样例 #1

输入 #1

3 2 -2
1 2 3

输出 #1

Yes
LDR

输入输出样例 #2

输入 #2

2 1 0
1 6

输出 #2

No

输入输出样例 #3

输入 #3

5 6 7
1 3 5 7 9

输出 #3

Yes
LRLUR

说明/提示

数据范围

• $1\leq N\leq 2000$
• $|A|, |B| \leq 3.6\times 10^6$
• $1\leq D_i\leq 1800$
• 输入均为整数。

样例解释 1

第 $1$ 次跳跃向左，第 $2$ 次跳跃向下，第 $3$ 次跳跃向右，则高桥君的移动为 $(0,0)\to(-1,0)\to(-1,-2)\to(2,-2)$，最终到达 $(2,-2)$，满足条件。

样例解释 2

经过 $2$ 次跳跃后，无法恰好到达 $(1,0)$。

由 ChatGPT 4.1 翻译