Pinely Round 4 (Div. 1 + Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ из $$$n$$$ целых чисел.
За одну операцию вы можете выполнить следующее двухэтапное действие:
Например, при выборе $$$x = 8$$$ массив $$$[5, 7, 10]$$$ изменится на $$$[|5-8|, |7-8|, |10-8|] = [3,1,2]$$$.
Постройте последовательность операций, чтобы сделать все элементы $$$a$$$ равными $$$0$$$ не более чем за $$$40$$$ операций или определите, что это невозможно. Вам не нужно минимизировать количество операций.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число $$$-1$$$, если невозможно сделать все элементы массива равными $$$0$$$ не более чем за $$$40$$$ операций.
В противном случае выведите две строки. Первая строка должна содержать одно целое число $$$k$$$ ($$$0 \le k \le 40$$$) — количество операций. Вторая строка должна содержать $$$k$$$ целых чисел $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i \le 10^{9}$$$) — последовательность операций, обозначающую, что на $$$i$$$-й операции вы выбрали $$$x=x_i$$$.
Если существует несколько решений, выведите любое из них.
Вам не обязательно минимизировать количество операций.
51520 034 6 8480 40 20 1051 2 3 4 5
1 5 0 3 6 1 1 7 60 40 20 10 30 25 5 -1
В первом наборе входных данных мы можем получить нужный массив за одну операцию, выбрав $$$x = 5$$$ и изменив массив с $$$[5]$$$ на $$$[0]$$$.
Во втором наборе входных данных никаких операций не требуется, поскольку все элементы массива уже равны $$$0$$$.
В третьем наборе входных данных мы можем выбрать $$$x = 6$$$, чтобы изменить массив с $$$[4, 6, 8]$$$ на $$$[2, 0, 2]$$$, затем выбрать $$$x = 1$$$, чтобы изменить его на $$$[1, 1, 1]$$$, и, наконец, снова выбрать $$$x = 1$$$, чтобы изменить массив на $$$[0, 0, 0]$$$.
В четвертом наборе входных данных мы можем сделать все элементы равными $$$0$$$, выполнив последовательность операций $$$(60, 40, 20, 10, 30, 25, 5)$$$.
В пятом наборе входных данных можно показать, что невозможно сделать все элементы равными $$$0$$$ не более чем за $$$40$$$ операций. Поэтому ответом будет $$$-1$$$.
Название |
---|