#P13281. [ABC111D] Robot Arms

    ID: 12464 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>CF2100提高奇偶性分析坐标变换序列构造

[ABC111D] Robot Arms

题目描述

在すぬけ君的工厂里,计划引进一种具有以下特性的机器人手臂:

  • 机器人手臂由 mm 个手臂和 m+1m+1 个关节组成。手臂编号为 1,2,...,m1, 2, ..., m,关节编号为 0,1,...,m0, 1, ..., m。手臂 ii 连接关节 i−1i-1 和关节 ii。手臂 ii 的长度为 did_i。
  • 每个手臂都可以独立指定模式。模式可以是 L、R、D、U 中的任意一个,手臂的模式决定了该手臂的方向。将工厂视为坐标平面时,关节 ii 的坐标 (xi,yi)(x_i, y_i) 按如下方式确定:
    • (x0,y0)=(0,0) (x_0, y_0) = (0, 0) 。
    • 当手臂 ii 的模式为 L 时,(xi,yi)=(xi−1−di,yi−1) (x_i, y_i) = (x_{i-1} - d_i, y_{i-1}) 。
    • 当手臂 ii 的模式为 R 时,(xi,yi)=(xi−1+di,yi−1) (x_i, y_i) = (x_{i-1} + d_i, y_{i-1}) 。
    • 当手臂 ii 的模式为 D 时,(xi,yi)=(xi−1,yi−1−di) (x_i, y_i) = (x_{i-1}, y_{i-1} - d_i) 。
    • 当手臂 ii 的模式为 U 时,(xi,yi)=(xi−1,yi−1+di) (x_i, y_i) = (x_{i-1}, y_{i-1} + d_i) 。

すぬけ君希望通过巧妙地指定手臂的模式,使得机器人手臂的关节 mm 能恰好到达 NN 个点 (X1,Y1),(X2,Y2),...,(XN,YN)(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N) 中的任意一个。请判断是否存在这样的机器人手臂。如果存在,请给出满足条件的机器人手臂,以及对于每个点 (Xj,Yj)(X_j, Y_j),使机器人手臂的关节 mm 到达该点的模式指定方法。

输入格式

输入按以下格式从标准输入读入。

NN
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮\vdots
XNX_N YNY_N

输出格式

如果存在满足条件的方案,请按以下格式输出。如果不存在,输出 -1。

mm
d1d_1 d2d_2 …\ldots dmd_m
w1w_1
w2w_2
⋮\vdots
wNw_N

其中,mm 和 did_i 表示机器人手臂的信息,具体含义见题目描述。要求 1≤m≤401 \leq m \leq 40,1≤di≤10121 \leq d_i \leq 10^{12},且 m,dim, d_i 均为整数。

wjw_j 是长度为 mm 的字符串,表示使机器人手臂的关节 mm 到达点 (Xj,Yj)(X_j, Y_j) 的模式指定方法。wjw_j 的第 ii 个字符为 L、R、D、U 中的一个,表示手臂 ii 的模式。

输入输出样例 #1

输入 #1

3
-1 0
0 3
2 -1

输出 #1

2
1 2
RL
UU
DR

输入输出样例 #2

输入 #2

5
0 0
1 0
2 0
3 0
4 0

输出 #2

-1

输入输出样例 #3

输入 #3

2
1 1
1 1

输出 #3

2
1 1
RU
UR

输入输出样例 #4

输入 #4

3
-7 -3
7 3
-3 -7

输出 #4

5
3 1 4 1 5
LRDUL
RDULR
DULRD

说明/提示

限制条件

  • 输入均为整数。
  • 1≤N≤10001 \leq N \leq 1000
  • −109≤Xi≤109-10^9 \leq X_i \leq 10^9
  • −109≤Yi≤109-10^9 \leq Y_i \leq 10^9

部分得分

  • 对于 300300 分的测试点,有 −10≤Xi≤10-10 \leq X_i \leq 10 且 −10≤Yi≤10-10 \leq Y_i \leq 10。

样例解释 1

对于每个 (Xj,Yj)(X_j, Y_j),使机器人手臂的关节 mm 到达该点的方法如下:

  • 对于 (X1,Y1)=(−1,0)(X_1, Y_1) = (-1, 0),首先关节 00 的位置为 (x0,y0)=(0,0)(x_0, y_0) = (0, 0)。手臂 11 的模式为 R,所以关节 11 的位置为 (x1,y1)=(1,0)(x_1, y_1) = (1, 0)。手臂 22 的模式为 L,所以关节 m=2m=2 的位置为 (x2,y2)=(−1,0)(x_2, y_2) = (-1, 0)。
  • 对于 (X2,Y2)=(0,3)(X_2, Y_2) = (0, 3),$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3)$。
  • 对于 (X3,Y3)=(2,−1)(X_3, Y_3) = (2, -1),$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1)$。

样例解释 3

(Xj,Yj)(X_j, Y_j) 中可能包含相同的点。