← 返回题目列表

AtCoder · k4pc_f

F. 无标题

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

問題文

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
问题: japlj
测试仪: 卡加米兹