問題文
Kagamizu 先生正在考虑送给他的儿子 Cucumber 一份圣诞礼物。
Kagamizu 先生有一定的担忧。 Cucumber 喜欢竞技性编程,因此存在这样的风险:他可能会受到竞赛中常见的奇怪问句的启发,并要求数组或图表作为礼物。
镜水先生觉得还是尽快问一下比较好,以免他突然问起来惊慌失措,于是他问黄瓜想要什么圣诞礼物。然后,黄瓜回答如下。
“我想要一个自然的问题设置来解决我要讨论的问题!”
課題
1 论维度空间 有 N 点,i 第一点 P_i 的坐标是 X_i 。
现在,通过添加一些新点, 我希望 N 点满足特定条件。条件是 N 元素的整数序列 K, D 表达如下。 对于
- 条件: i = 1, ..., N ,点 到第 P_i 到 K_i 个最近点的距离是 D_i 。然而,2 点之间的距离是其坐标差的绝对值。
距离考虑的点不仅是新添加的点,还包括现有的点。 N 点也被考虑。也就是说,从某个点 1 最近的点被认为是其自身。
通过添加一些点来判断是否可以满足上述条件。如果可能的话,要添加的点数为 10^5 还判断数量是否可以减少到小于 1 找到一个。
但是,X_i, D_i 和要添加的点的坐标均为整数。另外,要添加的点的坐标为 32 必须在位有符号整数可以表示的范围内。
从一开始就存在 请注意,对于 N 点和要添加的点,同一坐标处可能有多个点。
制約
所有输入数据满足以下约束。
- 1 ≦ N ≦ 10^3.
- -10^9 ≦ X_i ≦ 10^9.
- 1 ≦ K_i ≦ 10^9.
- 0 ≦ D_i ≦ 10^9.
此外,针对此问题设置了部分分数。2 点的输入数据还满足以下约束。
- N ≦ 10.
- K_i = 2.
入力
N X_1 K_1 D_1 : X_N K_N D_N
出力
如果无论怎么加分都无法满足问题的条件,
输出 impossible 。
可以添加积分来满足条件,但是无论添加多少积分,
如果超过 10^5 如果通过添加 too many 。
10^5 或更少的点即可满足条件,则按以下格式输出具体示例。
M A_1 … A_M
但是,M 是要添加的点数 A_j 是要添加的点的坐标。在这里,M 的值为 10^5 和每个 A_j 的值为 32 必须在位有符号整数可以表示的范围内。 此外,输出中不应有多余的空行或空格。 (16:36 补充)
入力例1
2 0 2 1 2 2 1
出力例1
1 1
要添加的点数为 10^5 只要小于或等于就不必是最小值,因此对于此问题也允许以下输出。
2 -1 1
入力例2
2 0 2 1 3 2 1
出力例2
2 -1 2
入力例3
1 1 1 1
出力例3
impossible
到一个点最近的点是它本身,它的距离是 请注意 0 。
入力例4
1 1 114514 1
出力例4
too many
例如坐标 2 至
通过放置 114,513 点即可满足该条件。然而,
因为在10^5 内无法满足条件 too many 。
入力例5
1 1 1 0
出力例5
0注意不要在这种情况下添加不必要的空行。 (16:36 添加)
问题: japlj
测试仪: 卡加米兹