CF336C.Vasily the Bear and Sequence

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Vasily the bear has got a sequence of positive integers _a_1, _a_2, ..., a__n. Vasily the Bear wants to write out several numbers on a piece of paper so that the beauty of the numbers he wrote out was maximum.

The beauty of the written out numbers _b_1, _b_2, ..., b__k is such maximum non-negative integer v, that number _b_1 and b_2 and ... and b__k is divisible by number 2_v without a remainder. If such number v doesn't exist (that is, for any non-negative integer v, number _b_1 and b_2 and ... and b__k is divisible by 2_v without a remainder), the beauty of the written out numbers equals -1.

Tell the bear which numbers he should write out so that the beauty of the written out numbers is maximum. If there are multiple ways to write out the numbers, you need to choose the one where the bear writes out as many numbers as possible.

Here expression x and y means applying the bitwise AND operation to numbers x and y. In programming languages C++ and Java this operation is represented by "&", in Pascal — by "and".

瓦西里熊有一个正整数序列 a1,a2,…,ana_1, a_2, \dots, a_n。瓦西里熊希望在一张纸上写出若干个数,使得所写出数字的“美感”(beauty)最大。

所写出数字 b1,b2,…,bkb_1, b_2, \dots, b_k 的美感定义为满足以下条件的最大非负整数 vv:数 b1andb2and⋯andbkb_1 \mathbin{\text{and}} b_2 \mathbin{\text{and}} \dots \mathbin{\text{and}} b_k 能被 2v2^v 整除(即无余数)。若这样的 vv 不存在(即对任意非负整数 vv,b1andb2and⋯andbkb_1 \mathbin{\text{and}} b_2 \mathbin{\text{and}} \dots \mathbin{\text{and}} b_k 均能被 2v2^v 整除),则所写出数字的美感定义为 −1-1。

请告诉瓦西里熊应写出哪些数字,才能使所写出数字的美感最大。若存在多种方案可达到最大美感,则需从中选择写出数字个数最多的方案。

此处表达式 xandyx \mathbin{\text{and}} y 表示对整数 xx 和 yy 执行按位与(bitwise AND)运算。在编程语言 C++ 和 Java 中该运算符记为 &,在 Pascal 中记为 and。

输入格式

The first line contains integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ _a_1 < _a_2 < ... < a__n ≤ 109).

第一行包含一个整数 nn(1 ≤ n ≤ 1051 \le n \le 10^5)。第二行包含 nn 个以空格分隔的整数 a1, a2, ..., ana_1,\,a_2,\,...,\,a_n(1 ≤ a1 < a2 < ... < an ≤ 1091 \le a_1 < a_2 < ... < a_n \le 10^9)。

输出格式

In the first line print a single integer k (k > 0), showing how many numbers to write out. In the second line print k integers _b_1, _b_2, ..., b__k — the numbers to write out. You are allowed to print numbers _b_1, _b_2, ..., b__k in any order, but all of them must be distinct. If there are multiple ways to write out the numbers, choose the one with the maximum number of numbers to write out. If there still are multiple ways, you are allowed to print any of them.

第一行输出一个整数 kk(k>0k > 0),表示需要写出的数字个数。
第二行输出 kk 个整数 b1, b2, …, bkb_1,\ b_2,\ \dots,\ b_k —— 需要写出的数字。
允许以任意顺序输出数字 b1, b2, …, bkb_1,\ b_2,\ \dots,\ b_k,但它们必须互不相同。
若存在多种方案可写出数字,则选择所写数字个数 kk 最大的方案;
若仍存在多种方案,则可任选其中一种输出。

输入输出样例

  • 输入#1

    5
    1 2 3 4 5

    输出#1

    2
    4 5
  • 输入#2

    3
    1 2 4

    输出#2

    1
    4

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

首页