Codeforces Round 669 (Div. 2) |
---|
Закончено |
У Александры есть массив $$$a$$$ четной длины, состоящий из чисел $$$0$$$ и $$$1$$$. Элементы массива пронумерованы от $$$1$$$ до $$$n$$$. Она хочет удалить из него не более $$$\frac{n}{2}$$$ элементов (где $$$n$$$ — его длина) таким образом, чтобы знакопеременная сумма массива была равна $$$0$$$ (т.е. $$$a_1 - a_2 + a_3 - a_4 + \dotsc = 0$$$). Иными словами, Александра хочет, чтобы сумма всех элементов на нечетных позициях была равна сумме всех элементов на четных позициях. Элементы, которые вы удаляете, не обязаны быть последовательными.
К примеру, если у нее был массив $$$a = [1, 0, 1, 0, 0, 0]$$$, и она удалила $$$2$$$-й и $$$4$$$-й элементы, то $$$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$$$) — число элементов, которые останутся после удаления. В следующей строке выведите $$$k$$$ чисел, которые не будут удалены, в том порядке, в котором они идут в массиве $$$a$$$. Обратите внимание, вам надо вывести сами числа, а не их индексы.
Можно показать, что ответ всегда существует. Если существует несколько ответов, выведите любой из них.
4 2 1 0 2 0 0 4 0 1 1 1 4 1 1 0 0
1 0 1 0 2 1 1 4 1 1 0 0
В первом и втором наборах входных данных знакопеременная сумма массива, очевидно, равна $$$0$$$.
В третьем наборе входных данных знакопеременная сумма массива равна $$$1 - 1 = 0$$$.
В четвертом наборе входных данных знакопеременная сумма уже равна $$$1 - 1 + 0 - 0 = 0$$$, мы можем ничего не удалять.
Название |
---|