← 返回题目列表

Codeforces · 1689/E

E. 无限与

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

Bit Lightyear,通往 ANDfinity 及更远!

从计算机科学专业毕业后,Vlad 获得了一个由 $$$n$$$ 非负整数组成的数组 $$$a_1,a_2,\ldots,a_n$$$。很自然地,他想构造一个由 $$$n$$$ 个顶点组成的图,编号为 $$$1, 2,\ldots, n$$$。他决定当且仅当 $$$a_i \& a_j > 0$$$ 时在 $$$i$$$ 和 $$$j$$$ 之间添加一条边,其中 $$$\&$$$ 表示按位 AND 运算。

Vlad 还希望将图连接起来,但最初情况可能并非如此。为了满足这一点,他可以对数组进行以下两种类型的操作:

1. 选择某个元素 $$$a_i$$$ 并将其增加 $$$1$$$。
2. 选择某个元素 $$$a_i$$$ 并将其递减 $$$1$$$(仅当 $$$a_i > 0$$$ 时才可能)。

可以证明存在有限的操作序列使得图将被连接。那么,您能否帮助 Vlad 找到执行此操作所需的最少操作数,并提供执行此操作的方法?

输入

输入数据中有多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。接下来是测试用例描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n \leq 2000$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i < 2^{30}$$$) - 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,在第一行打印一个整数 $$$m$$$ — 最小操作数。在第二行中,在完成有效的操作序列后打印数组,以便任务中的图形变为连接状态。

如果有多个解,则输出任意一个。

示例

输入 #1

4
5
1 2 3 4 5
2
0 2
2
3 12
4
3 0 0 0

输出 #1

0
1 2 3 4 5
2
2 2
1
3 11
3
3 1 1 1

注意

在第一个测试用例中,图已经连接。

在第二个测试用例中,我们可以将 $$$0$$$ 递增两次,最终得到数组 $$$[2,2]$$$。由于 $$$2 \& 2 = 2 > 0$$$,该图是连通的。可见,一次操作是不够的。

在第三个测试用例中,我们可以将 $$$12$$$ 递减一次,最终得到一个数组 $$$[3,11]$$$。 $$$3 \& 11 = 3 > 0$$$ 因此图是连通的。由于图形一开始并未连接,因此必须执行一次操作。