← 返回题目列表

Codeforces · 1901/C

C. 加法、除法和下限

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

给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。在一次操作中,您可以选择一个整数 $$$x$$$ ($$$0 \le x \le 10^{18}$$$) 并将 $$$a_i$$$ 替换为 $$$\lfloor \frac{a_i + x}{2} \rfloor$$$ ($$$\lfloor y \rfloor$$$ 表示将 $$$y$$$ 向下舍入到最接近的整数) $$$i$$$ 从 $$$1$$$ 到 $$$n$$$。请注意,每次操作都会影响数组的所有元素。

打印使数组的所有元素相等所需的最少操作数。

如果操作数小于或等于 $$$n$$$,则为每个操作打印所选的 $$$x$$$。如果有多个答案,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印使数组的所有元素相等所需的最少操作数。

如果操作数小于或等于 $$$n$$$,则在下一行中为每个操作打印所选的 $$$x$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32

输出 #1

0
2
2 5
1
1
6

注意

在第一个测试用例中,所有元素都已经相等,因此需要 $$$0$$$ 操作。之后是否打印空行并不重要。

在第二个测试用例中,您不能进行少于 $$$2$$$ 的操作。有多个答案,让我们考虑答案序列$$$[2, 5]$$$。应用 $$$x = 2$$$ 运算后,数组变为 $$$[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$$$。之后应用 $$$x = 5$$$ 运算后,数组变为 $$$[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$$$。两个元素是相同的,所以我们就完成了。

在最后一个测试用例中,您不能进行少于 $$$6$$$ 的操作。由于 $$$6$$$ 大于 $$$n$$$,因此您不必打印它们。一种可能的答案序列是 $$$[0, 0, 0, 0, 0, 0]$$$。我们只是每次将第二个元素除以$$$2$$$,而不更改第一个元素。