CF988D.Points and Powers of Two

普及+/提高

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are nn distinct points on a coordinate line, the coordinate of ii-th point equals to xix_i. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points xi1,xi2,…,ximx_{i_1}, x_{i_2}, \dots, x_{i_m} such that for each pair xijx_{i_j}, xikx_{i_k} it is true that ∣xij−xik∣=2d|x_{i_j} - x_{i_k}| = 2^d where dd is some non-negative integer number (not necessarily the same for each pair of points).

在一条坐标轴上有 nn 个互不相同的点,其中第 ii 个点的坐标为 xix_i。请从给定的点集中选出一个子集,使得该子集中任意两点之间的距离均为 22 的整数次幂(即形如 2d2^d,其中 dd 为非负整数)。注意:需考虑子集中所有点对(而不仅限于相邻点对)。特别地,任何只含一个元素的子集均满足上述条件。在所有满足条件的子集中,找出元素个数最多的那个子集。

换言之,你需要选出尽可能多的点 xi1,xi2,…,ximx_{i_1}, x_{i_2}, \dots, x_{i_m},使得对任意一对点 xijx_{i_j}、xikx_{i_k},均有 ∣xij−xik∣=2d|x_{i_j} - x_{i_k}| = 2^d,其中 dd 是某个非负整数(不同点对的 dd 值可以不同)。

输入格式

The first line contains one integer nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) — the number of points.

The second line contains nn pairwise distinct integers x1,x2,…,xnx_1, x_2, \dots, x_n (−109≤xi≤109-10^9 \le x_i \le 10^9) — the coordinates of points.

第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)—— 点的数量。

第二行包含 nn 个两两不同的整数 x1,x2,…,xnx_1, x_2, \dots, x_n(−109≤xi≤109-10^9 \le x_i \le 10^9)—— 各点的坐标。

输出格式

In the first line print mm — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print mm integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

第一行输出 mm —— 满足上述条件的子集中点数的最大可能值。

第二行输出 mm 个整数 —— 你所选择的子集中各点的坐标。

若存在多个答案,输出任意一个即可。

输入输出样例

  • 输入#1

    6
    3 5 4 7 10 12

    输出#1

    3
    7 3 5
  • 输入#2

    5
    -1 2 5 8 11

    输出#2

    1
    8

说明/提示

In the first example the answer is [7,3,5][7, 3, 5]. Note, that ∣7−3∣=4=22|7-3|=4=2^2, ∣7−5∣=2=21|7-5|=2=2^1 and ∣3−5∣=2=21|3-5|=2=2^1. You can't find a subset having more points satisfying the required property.

在第一个例子中,答案是 [7,3,5][7, 3, 5]。注意,∣7−3∣=4=22|7-3|=4=2^2,∣7−5∣=2=21|7-5|=2=2^1,且 ∣3−5∣=2=21|3-5|=2=2^1。你无法找到满足该性质的、包含更多点的子集。

输入解题思路,AI测评打分。不知道怎么写?

首页