Robot Rotation

题目描述

一个机器人位于坐标平面的原点，正 $x$ $-$ 轴指向右方，正 $y$ $-$ 轴指向上方。最初，机器人面向正 $x$ 方向。 对于 $i=1,\ldots,N$，按此顺序执行以下操作。

将机器人旋转 $90$ 度，顺时针或逆时针均可。然后，机器人沿其面向的方向前进 $A_i$ 单位。

是否可以选择每次旋转的方向，使得机器人在 $N$ 次操作后位于坐标 $(X,Y)$？ 如果可能，确定每次操作应选择顺时针还是逆时针旋转。

输入格式

输入从标准输入按照以下格式给出： $N$ $X$ $Y$ $A_1$ $\ldots$ $A_N$

输出格式

如果机器人在 $N$ 次操作后不能位于坐标 $(X,Y)$，则输出 $No$.
如果机器人在 $N$ 次操作后可以位于坐标 $(X,Y)$，第一行应包含 $Yes$，第二行应包含一个长度为 $N$ 的字符串 $S$，满足以下条件。
条件：$S$ 由 $L$ 和 $R$ 组成，且以下选择可以使机器人在 $N$ 次操作后位于坐标 $(X,Y)$：在第 $i$ 次操作中，如果 $S$ 的第 $i$ 个字符为 $L$ 则将机器人逆时针旋转，第 $i$ 个字符为 $R$ 则将机器人顺时针旋转。 如果存在多个解，则可以输出任意一个。

3 -2 4
3 2 1

Yes
LLR

1 0 0
1

No

4 0 0
1 1 1 1

Yes
LRRR

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

Yes
LLLLLLLLLRLRRR

提示

$1 \leq N \leq 80$ $1 \leq A_i \leq 10^7$ $-10^9\leq X,Y \leq 10^9$ 所有输入值均为整数。最初，机器人位于 $(0,0)$ 并面向正 $x$ 方向。下面的选择可以使机器人在 $N$ 次操作后位于坐标 $(X,Y)$。

第一次操作：将机器人逆时针旋转 $90$ 度，使其面向正 $y$ 方向。机器人沿其面向的方向前进 $A_1=3$ 单位，移动到 $(0,3)$。 第二次操作：将机器人逆时针旋转 $90$ 度，使其面向负 $x$ 方向。机器人沿其面向的方向前进 $A_2=2$ 单位，移动到 $(-2,3)$。 第三次操作：将机器人顺时针旋转 $90$ 度，使其面向正 $y$ 方向。机器人沿其面向的方向前进 $A_3=1$ 单位，移动到 $(-2,4)$。

诸如 $LLLL$ 和 $RRRR$ 的输出也被接受。

标签: AtCoder|abc326F

来源

AtCoder|abc326F