/ 
実行時間制限: 5 sec / メモリ制限: 1024 MB
問題文
無限に広がる 2 次元の座標平面を考えます。 高橋君は最初 (0,0) に立っており、今から上下左右いずれかの方向を選んでジャンプすることを N 回行います。 それぞれのジャンプで移動する距離は定まっており、具体的には i 回目のジャンプでは距離 D_i を移動します。 N 回のジャンプの後で、ちょうど位置 (A,B) にいるようにすることは可能か判定し、 可能ならばそのような移動方法を 1 つ示してください。
ただし、現在の位置が (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)
制約
- 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 を 1 行目に出力せよ。
Yes の場合は 2 行目に条件をみたす移動方法を、U , D , L , R からなる長さ N の文字列 S として出力せよ。
ただし、S の i 文字目が
Uのとき、 i 回目のジャンプでは上方向に移動するDのとき、 i 回目のジャンプでは下方向に移動するLのとき、 i 回目のジャンプでは左方向に移動するRのとき、 i 回目のジャンプでは右方向に移動する
ことを指す。
入力例 1
3 2 -2 1 2 3
出力例 1
Yes LDR
1 回目のジャンプで左方向に、2 回目のジャンプで下方向に、3 回目のジャンプで右方向にジャンプすると、 (0,0)\to(-1,0)\to(-1,-2)\to(2,-2) と高橋君は動き、 最終的に (2,-2) に到達しているためこれは条件をみたしています。
入力例 2
2 1 0 1 6
出力例 2
No
2 回のジャンプの後でちょうど (1,0) にいるようにすることはできません。
入力例 3
5 6 7 1 3 5 7 9
出力例 3
Yes LRLUR
Score : 600 points
Problem Statement
Consider an infinite two-dimensional coordinate plane. Takahashi, who is initially standing at (0,0), will do N jumps in one of the four directions he chooses every time: up, down, left, or right. The length of each jump is fixed. Specifically, the i-th jump should cover the distance of D_i. Determine whether it is possible to be exactly at (A, B) after N jumps. If it is possible, show one way to do so.
Here, for each direction, a jump of length D from (X, Y) takes him to the following point:
- up: (X,Y) \to (X,Y+D)
- down: (X,Y) \to (X,Y-D)
- left: (X,Y) \to (X-D,Y)
- right: (X,Y) \to (X+D,Y).
Constraints
- 1 \leq N \leq 2000
- \lvert A\rvert, \lvert B\rvert \leq 3.6\times 10^6
- 1 \leq D_i \leq 1800
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B D_1 D_2 \ldots D_N
Output
In the first line, print Yes if there is a desired sequence of jumps, and No otherwise.
In the case of Yes, print in the second line a desired sequence of jumps as a string S of length N consisting of U , D , L , R, as follows:
- if the i-th jump is upward, the i-th character should be
U; - if the i-th jump is downward, the i-th character should be
D; - if the i-th jump is to the left, the i-th character should be
L; - if the i-th jump is to the right, the i-th character should be
R.
Sample Input 1
3 2 -2 1 2 3
Sample Output 1
Yes LDR
If he jumps left, down, right in this order, Takahashi moves (0,0)\to(-1,0)\to(-1,-2)\to(2,-2) and ends up at (2, -2), which is desired.
Sample Input 2
2 1 0 1 6
Sample Output 2
No
It is impossible to be exactly at (1, 0) after the two jumps.
Sample Input 3
5 6 7 1 3 5 7 9
Sample Output 3
Yes LRLUR