← 返回题目列表

AtCoder · arc103_b

D. 机器人手臂

中文机器翻译题面 查看原题

分数: 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 is L,关节位置 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