← 返回题目列表

Codeforces · 1407/A

A. 啊哈哈哈哈哈哈哈哈哈

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

Alexandra 有一个偶数长度数组 $$$a$$$,由 $$$0$$$ 和 $$$1$$$ 组成。数组的元素从 $$$1$$$ 到 $$$n$$$ 进行枚举。她希望最多删除 $$$\frac{n}{2}$$$ 个元素(其中 $$$n$$$ — 数组的长度),使得数组的交替总和等于 $$$0$$$ (即 $$$a_1 - a_2 + a_3 - a_4 + \dotsc = 0$$$)。换句话说,Alexandra 希望奇数位置的所有元素的总和与偶数位置的所有元素的总和相等。您删除的元素不必是连续的。

例如,如果她有 $$$a = [1, 0, 1, 0, 0, 0]$$$ 并且删除了 $$$2$$$nd 和 $$$4$$$th 元素,$$$a$$$ 将变得等于 $$$[1, 1, 0, 0]$$$ 并且其交替总和为 $$$1 - 1 + 0 - 0 = 0$$$。

帮助她!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^3$$$, $$$n$$$ 是偶数) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — 数组的元素。

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

输出

对于每个测试用例,首先打印 $$$k$$$ ($$$\frac{n}{2} \leq k \leq n$$$) — 按照 $$$a$$$ 中出现的顺序删除后保留的元素数量。然后,打印这个 $$$k$$$ 数字。请注意,您应该打印数字本身,而不是它们的索引。

我们可以证明答案总是存在的。如果有多个答案,则可以输出其中任何一个。

示例

输入 #1

4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0

输出 #1

1
0
1
0
2
1 1
4
1 1 0 0

注意

在第一种和第二种情况下,数组的交替总和显然等于 $$$0$$$。

在第三种情况下,数组的交替和等于 $$$1 - 1 = 0$$$。

在第四种情况下,交替总和已经等于 $$$1 - 1 + 0 - 0 = 0$$$,因此我们不必删除任何内容。