[ARC103B] Robot Arms
题意翻译
给定 $n$ 组坐标。构造长度为 $m$ 的序列 $\{c_n\}$ 和 $n$ 组包含 `LRUD` 的路径,满足对于每一组坐标:
- $c_i$ 表示第 $i$ 步「步长」。
- 对于每个坐标,从 $(0,0)$ 开始走,共走 $m$ 步。第 $i$ 步可以让 $(x,y)$ 变成 $(x±c_i,y)$ 或 $(x,y±c_i)$ 。
- 走完 $m$ 次之后,恰好走到这组坐标。
- 要求 $m\leq 40,c_i\leq 10^{12}$ 。
$1\leq n\leq 1000$
题目描述
[problemUrl]: https://abc111.contest.atcoder.jp/tasks/arc103_b
すぬけ君の工場では,次のような特徴を持つ **ロボットアーム** を導入することになりました:
- ロボットアームは, $ m $ 個の **腕** と $ m+1 $ 個の **関節** からなる.腕には $ 1 $ , $ 2 $ , ..., $ m $ で,関節には $ 0 $ , $ 1 $ , ..., $ m $ で番号が付けられている.腕 $ i $ は関節 $ i-1 $ と関節 $ i $ をつなぐ.腕 $ i $ の長さは $ d_i $ である.
- 各腕には,それぞれ独立に **モード** を指定することができる.モードは `L`, `R`, `D`, `U` のいずれかであり,腕のモードはその腕の向きを指定する.工場を座標平面とみなすと,関節 $ i $ の座標 $ (x_i,\ y_i) $ は次のように定まる:
- $ (x_0,\ y_0)\ =\ (0,\ 0) $ .
- 腕 $ i $ のモードが `L` のとき, $ (x_i,\ y_i)\ =\ (x_{i-1}\ -\ d_{i},\ y_{i-1}) $ .
- 腕 $ i $ のモードが `R` のとき, $ (x_i,\ y_i)\ =\ (x_{i-1}\ +\ d_{i},\ y_{i-1}) $ .
- 腕 $ i $ のモードが `D` のとき, $ (x_i,\ y_i)\ =\ (x_{i-1},\ y_{i-1}\ -\ d_{i}) $ .
- 腕 $ i $ のモードが `U` のとき, $ (x_i,\ y_i)\ =\ (x_{i-1},\ y_{i-1}\ +\ d_{i}) $ .
すぬけ君は,腕のモードをうまく指定することにより, $ N $ 個の点 $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ ...,\ (X_N,\ Y_N) $ のいずれにもロボットアームの関節 $ m $ をちょうど一致させられるようなロボットアームを導入したいです. このようなことは可能でしょうか? 可能ならば,条件を満たすロボットアームおよび,各点 $ (X_j,\ Y_j) $ にそのロボットアームの関節 $ m $ を到達させるためのモードの指定方法を求めてください.
Snuke is introducing a **robot arm** with the following properties to his factory:
- The robot arm consists of $ m $ **sections** and $ m+1 $ **joints**. The sections are numbered $ 1 $ , $ 2 $ , ..., $ m $ , and the joints are numbered $ 0 $ , $ 1 $ , ..., $ m $ . Section $ i $ connects Joint $ i-1 $ and Joint $ i $ . The length of Section $ i $ is $ d_i $ .
- For each section, its **mode** can be specified individually. There are four modes: `L`, `R`, `D` and `U`. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint $ i $ will be determined as follows (we denote its coordinates as $ (x_i,\ y_i) $ ):
- $ (x_0,\ y_0)\ =\ (0,\ 0) $ .
- If the mode of Section $ i $ is `L`, $ (x_{i},\ y_{i})\ =\ (x_{i-1}\ -\ d_{i},\ y_{i-1}) $ .
- If the mode of Section $ i $ is `R`, $ (x_{i},\ y_{i})\ =\ (x_{i-1}\ +\ d_{i},\ y_{i-1}) $ .
- If the mode of Section $ i $ is `D`, $ (x_{i},\ y_{i})\ =\ (x_{i-1},\ y_{i-1}\ -\ d_{i}) $ .
- If the mode of Section $ i $ is `U`, $ (x_{i},\ y_{i})\ =\ (x_{i-1},\ y_{i-1}\ +\ d_{i}) $ .
Snuke would like to introduce a robot arm so that the position of Joint $ m $ can be matched with all of the $ N $ points $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ ...,\ (X_N,\ Y_N) $ by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint $ m $ to each point $ (X_j,\ Y_j) $ .
输入输出格式
输入格式
Input is given from Standard Input in the following format:
```
$ N $
$ X_1 $ $ Y_1 $
$ X_2 $ $ Y_2 $
$ : $
$ X_N $ $ Y_N $
```
输出格式
If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print `-1`.
```
$ m $
$ d_1 $ $ d_2 $ $ ... $ $ d_m $
$ w_1 $
$ w_2 $
$ : $
$ w_N $
```
$ m $ and $ d_i $ are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, $ 1\ \leq\ m\ \leq\ 40 $ and $ 1\ \leq\ d_i\ \leq\ 10^{12} $ must hold. Also, $ m $ and $ d_i $ must all be integers.
$ w_j $ is a string of length $ m $ that represents the way to bring Joint $ m $ of the robot arm to point $ (X_j,\ Y_j) $ . The $ i $ -th character of $ w_j $ should be one of the letters `L`, `R`, `D` and `U`, representing the mode of Section $ i $ .
输入输出样例
输入样例 #1
3
-1 0
0 3
2 -1
输出样例 #1
2
1 2
RL
UU
DR
输入样例 #2
5
0 0
1 0
2 0
3 0
4 0
输出样例 #2
-1
输入样例 #3
2
1 1
1 1
输出样例 #3
2
1 1
RU
UR
输入样例 #4
3
-7 -3
7 3
-3 -7
输出样例 #4
5
3 1 4 1 5
LRDUL
RDULR
DULRD
输入样例 #5
3
-1 0
0 3
2 -1
输出样例 #5
2
1 2
RL
UU
DR
输入样例 #6
5
0 0
1 0
2 0
3 0
4 0
输出样例 #6
-1
输入样例 #7
2
1 1
1 1
输出样例 #7
2
1 1
RU
UR
输入样例 #8
3
-7 -3
7 3
-3 -7
输出样例 #8
5
3 1 4 1 5
LRDUL
RDULR
DULRD
说明
### 制約
- 入力はすべて整数である
- $ 1\ \leq\ N\ \leq\ 1000 $
- $ -10^9\ \leq\ X_i\ \leq\ 10^9 $
- $ -10^9\ \leq\ Y_i\ \leq\ 10^9 $
### 部分点
- $ 300 $ 点分のテストケースでは, $ -10\ \leq\ X_i\ \leq\ 10 $ および $ -10\ \leq\ Y_i\ \leq\ 10 $ が成り立つ.
### Constraints
- All values in input are integers.
- $ 1\ \leq\ N\ \leq\ 1000 $
- $ -10^9\ \leq\ X_i\ \leq\ 10^9 $
- $ -10^9\ \leq\ Y_i\ \leq\ 10^9 $
### Partial Score
- In the test cases worth $ 300 $ points, $ -10\ \leq\ X_i\ \leq\ 10 $ and $ -10\ \leq\ Y_i\ \leq\ 10 $ hold.
### Sample Explanation 1
それぞれの $ (X_j,\ Y_j) $ にロボットアームの関節 $ m $ を到達させる方法において,各関節の位置は次のようになります. - $ (X_1,\ Y_1)\ =\ (-1,\ 0) $ に到達させる方法では,まず関節 $ 0 $ の位置は $ (x_0,\ y_0)\ =\ (0,\ 0) $ です.腕 $ 1 $ のモードが `R` なので,関節 $ 1 $ の位置は $ (x_1,\ y_1)\ =\ (1,\ 0) $ です.腕 $ 2 $ のモードが `L` なので,関節 $ m=2 $ の位置は $ (x_2,\ y_2)\ =\ (-1,\ 0) $ です. - $ (X_2,\ Y_2)\ =\ (0,\ 3) $ に到達させる方法では, $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ 1),\ (x_2,\ y_2)\ =\ (0,\ 3) $ です. - $ (X_3,\ Y_3)\ =\ (2,\ -1) $ に到達させる方法では, $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ -1),\ (x_2,\ y_2)\ =\ (2,\ -1) $ です.
### Sample Explanation 3
$ (X_j,\ Y_j) $ の中に同じ点が含まれることもあります.
### Sample Explanation 5
In the given way to bring Joint $ m $ of the robot arm to each $ (X_j,\ Y_j) $ , the positions of the joints will be as follows: - To $ (X_1,\ Y_1)\ =\ (-1,\ 0) $ : First, the position of Joint $ 0 $ is $ (x_0,\ y_0)\ =\ (0,\ 0) $ . As the mode of Section $ 1 $ is `R`, the position of Joint $ 1 $ is $ (x_1,\ y_1)\ =\ (1,\ 0) $ . Then, as the mode of Section $ 2 $ is `L`, the position of Joint $ 2 $ is $ (x_2,\ y_2)\ =\ (-1,\ 0) $ . - To $ (X_2,\ Y_2)\ =\ (0,\ 3) $ : $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ 1),\ (x_2,\ y_2)\ =\ (0,\ 3) $ . - To $ (X_3,\ Y_3)\ =\ (2,\ -1) $ : $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ -1),\ (x_2,\ y_2)\ =\ (2,\ -1) $ .
### Sample Explanation 7
There may be duplicated points among $ (X_j,\ Y_j) $ .