分数: 600 点
问题陈述
Snuke 正在推出 机器人手臂 他的工厂具有以下属性:
- 机器人手臂包括 m 部分 和 m+1 关节。这些部分已编号 1, 2, ..., m,并且关节已编号 0, 1, ..., m。部分 i 连接关节 i-1 和联合 i。截面长度 i is d_i.
- 对于每个部分,其 模式 可以单独指定。有四种模式:
L,R,D和U。一个部分的模式决定了该部分的方向。如果我们将工厂视为一个坐标平面,则Joint的位置 i 将确定如下(我们将其坐标表示为 (x_i, y_i)):- (x_0, y_0) = (0, 0).
- 如果节的模式 i is
L, (x_{i}, y_{i}) = (x_{i-1} - d_{i}, y_{i-1}). - 如果节的模式 i is
R, (x_{i}, y_{i}) = (x_{i-1} + d_{i}, y_{i-1}). - 如果节的模式 i is
D, (x_{i}, y_{i}) = (x_{i-1}, y_{i-1} - d_{i}). - 如果节的模式 i is
U, (x_{i}, y_{i}) = (x_{i-1}, y_{i-1} + d_{i}).
Snuke想引入一个机械臂,以便关节的位置 m 可与所有 N 点 (X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N) 通过正确指定各部分的模式。 这可能吗? 如果是的话,找到这样的机械臂以及如何带关节 m 到每个点 (X_j, Y_j).
约束
- 输入中的所有值都是整数。
- 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 按住。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 : X_N Y_N
输出
如果可以满足条件,则遵循以下格式。如果条件不能满足,则打印 -1.
m d_1 d_2 ... d_m w_1 w_2 : w_N
m 和 d_i 是机器人手臂的配置。请参阅问题陈述以了解它们各自的含义。 在这里, 1 \leq m \leq 40 和 1 \leq d_i \leq 10^{12} 必须保留。另外, m 和 d_i 必须全部为整数。
w_j 是一个长度为的字符串 m 表示带联合的方式 m 机器人手臂的指向 (X_j, Y_j)。
的 i- 第一个字符 w_j 应该是字母之一 L, R, D 和 U,代表Section的模式 i.
示例输入 1
3 -1 0 0 3 2 -1
示例输出 1
2 1 2 RL UU DR
以给定的方式携带联合 m 机器人手臂到每个 (X_j, Y_j),关节的位置如下:
- To (X_1, Y_1) = (-1, 0):一、Joint的位置 0 is (x_0, y_0) = (0, 0)。作为Section的模式 1 is
R,关节位置 1 is (x_1, y_1) = (1, 0)。那么,作为Section的模式 2 isL,关节位置 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).
示例输入 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
之间可能存在重复点 (X_j, Y_j).
示例输入 4
3 -7 -3 7 3 -3 -7
示例输出 4
5 3 1 4 1 5 LRDUL RDULR DULRD