F - Robot Rotation Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

右向きを x 軸正方向、上向きを y 軸正方向とする座標平面の原点にロボットがいます。ロボットは最初、x 軸正方向を向いています。

i=1,\ldots,N の順に以下の操作を行います：

  • ロボットを右回りまたは左回りに 90 度回転させる。その後、ロボットは向いている方向に A_i 進む

回転方向を適切に選ぶことで、N 回の操作後にロボットがいる座標を (X,Y) にすることはできますか？

できるならば、各操作において、右回りと左回りのどちらを選べばよいか求めてください。

制約

  • 1 \leq N \leq 80
  • 1 \leq A_i \leq 10^7
  • -10^9\leq X,Y \leq 10^9
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N X Y
A_1 \ldots A_N

出力

N 回の操作後にロボットがいる座標を (X,Y) にできないとき、No と出力せよ。
N 回の操作後にロボットがいる座標を (X,Y) にできるとき、1行目に Yes と出力し、2行目に次の条件を満たす長さ N の文字列 S を出力せよ。
条件： S は L または R のみからなり、S の i 番目の文字が L ならば i 回目の操作においてロボットを左回りに、R ならばロボットを右回りに回転させることで、N 回の操作後にロボットがいる座標を (X,Y) にできる。

答えが複数ある場合はどれを出力しても正解となる。

入力例 1

3 -2 4
3 2 1

出力例 1

Yes
LLR

最初ロボットは (0,0) にいて、x 軸正方向を向いています。次の手順により、N 回の操作後にロボットがいる座標を (X,Y) にできます。

  • 1 回目の操作：ロボットを左に 90 度回転させ、y 軸正方向を向かせる。ロボットは向いている方向に A_1=3 進み、ロボットのいる座標は (0,3) となる。
  • 2 回目の操作：ロボットを左に 90 度回転させ、x 軸負方向を向かせる。ロボットは向いている方向に A_2=2 進み、ロボットのいる座標は (-2,3) となる。
  • 3 回目の操作：ロボットを右に 90 度回転させ、y 軸正方向を向かせる。ロボットは向いている方向に A_3=1 進み、ロボットのいる座標は (-2,4) となる。

図

入力例 2

1 0 0
1

出力例 2

No

入力例 3

4 0 0
1 1 1 1

出力例 3

Yes
LRRR

LLLL や RRRR などでも正解となります。

入力例 4

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

出力例 4

Yes
LLLLLLLLLRLRRR

Score : 525 points

Problem Statement

A robot is at the origin of a coordinate plane where the positive x-axis points to the right and the positive y-axis points upwards. Initially, the robot is facing the positive x-direction.

You will perform the following operation for i=1,\ldots,N in this order.

  • Rotate the robot 90 degrees clockwise or counterclockwise. Then, the robot moves forward A_i units in the direction it is facing.

Can the direction of rotation be chosen so that the robot will be at the coordinates (X,Y) after the N operations?

If it is possible, determine which direction, clockwise or counterclockwise, should be chosen for each operation.

Constraints

  • 1 \leq N \leq 80
  • 1 \leq A_i \leq 10^7
  • -10^9\leq X,Y \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Y
A_1 \ldots A_N

Output

If the robot cannot be at the coordinates (X,Y) after the N operations, print No.
If the robot can be at the coordinates (X,Y) after the N operations, the first line should contain Yes, and the second line should contain a string S of length N that satisfies the following condition.
Condition: S consists of L and R, and the following choices can put the robot at the coordinates (X,Y) after the N operations: in the i-th operation, rotate the robot counterclockwise if the i-th character of S is L, and rotate it clockwise if it is R.

If there are multiple solutions, you may print any of them.

Sample Input 1

3 -2 4
3 2 1

Sample Output 1

Yes
LLR

Initially, the robot is at (0,0) and facing the positive x-direction. The following choices can put the robot at the coordinates (X,Y) after the N operations.

  • First operation: Rotate the robot 90 degrees counterclockwise to face the positive y-direction. The robot moves forward A_1=3 units in the direction it is facing, and moves to (0,3).
  • Second operation: Rotate the robot 90 degrees counterclockwise to face the negative x-direction. The robot moves forward A_2=2 units in the direction it is facing, and moves to (-2,3).
  • Third operation: Rotate the robot 90 degrees clockwise to face the positive y-direction. The robot moves forward A_3=1 unit in the direction it is facing, and moves to (-2,4).

Diagram

Sample Input 2

1 0 0
1

Sample Output 2

No

Sample Input 3

4 0 0
1 1 1 1

Sample Output 3

Yes
LRRR

Outputs such as LLLL and RRRR are also accepted.

Sample Input 4

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

Sample Output 4

Yes
LLLLLLLLLRLRRR