← 返回题目列表

Codeforces · 988/D

D. 点和二的幂

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

坐标线上有$$$n$$$个不同的点,第$$$i$$$个点的坐标等于$$$x_i$$$。选择给定点集的子集,使得子集中每对点之间的距离是 2 的整数幂。需要考虑每一对点,而不仅仅是相邻的点。请注意,任何包含一个元素的子集都满足上述条件。在所有这些子集中,选择一个具有最大可能大小的子集。

换句话说,您必须选择最大可能的点数 $$$x_{i_1}, x_{i_2}, \dots, x_{i_m}$$$,使得对于每对 $$$x_{i_j}$$$, $$$x_{i_k}$$$ 确实 $$$|x_{i_j} - x_{i_k}| = 2^d$$$ 其中 $$$d$$$ 是一些非负整数(每对点不一定相同)。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 点数。

第二行包含 $$$n$$$ 成对不同的整数 $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$) — 点的坐标。

输出

在第一行中打印 $$$m$$$ — 满足上述条件的子集中可能的最大点数。

在第二行中打印 $$$m$$$ 整数 - 您选择的子集中点的坐标。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

6
3 5 4 7 10 12

输出 #1

3
7 3 5

输入 #2

5
-1 2 5 8 11

输出 #2

1
8

注意

在第一个示例中,答案是 $$$[7, 3, 5]$$$。请注意,$$$|7-3|=4=2^2$$$、$$$|7-5|=2=2^1$$$ 和 $$$|3-5|=2=2^1$$$。您无法找到具有更多满足所需属性的点的子集。