← 返回题目列表

Codeforces · 1965/D

D. 缺少子数组和

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

有一个包含 $$$n$$$ 正整数的隐藏数组 $$$a$$$。你知道 $$$a$$$ 是一个回文,或者换句话说,对于所有 $$$1 \le i \le n$$$,$$$a_i = a_{n + 1 - i}$$$。您将以任意顺序给出除其中一个不同子数组之外的所有子数组的总和。未给出总和的子数组可以是 $$$a$$$ 的任何 $$$\frac{n(n+1)}{2}$$$ 不同子数组。

恢复任何可能的回文$$$a$$$。选择输入时,始终至少有一个数组 $$$a$$$ 满足条件。

数组 $$$b$$$ 是 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 中删除几个(可能是零个或全部)元素并从末尾删除几个(可能是零个或全部)元素来获得。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的下一行包含 $$$\frac{n(n+1)}{2} - 1$$$ 整数 $$$s_i$$$ ($$$1\leq s_i \leq 10^9$$$) - 除了 $$$a$$$ 的一个子数组和之外的所有子数组和。

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

输入的附加约束:始终至少有一个有效的解决方案。

对于此问题,黑客已被禁用。

输出

对于每个测试用例,打印一行包含 $$$n$$$ 正整数 $$$a_1, a_2, \cdots a_n$$$ - 任何有效数组 $$$a$$$。请注意,$$$a$$$ 必须是回文。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000

输出 #1

1 2 1 
7 2 2 7 
3 5 5 3 
6 4 4 6 
1 1 1 1 1 
2 1 2 1 2 
500000000 500000000 500000000

注意

对于第一个示例,$$$a = [1, 2, 1]$$$ 的子数组为:

- $$$[1]$$$ 总和 $$$1$$$,
- $$$[2]$$$ 总和 $$$2$$$,
- $$$[1]$$$ 总和 $$$1$$$,
- $$$[1, 2]$$$,总和 $$$3$$$,
- $$$[2, 1]$$$,总和 $$$3$$$,
- $$$[1, 2, 1]$$$,总和 $$$4$$$。

对于第二个示例情况,对于子数组 $$$[2, 2]$$$,缺失的子数组总和为 $$$4$$$。

对于第三个示例,缺失的子数组总和为 $$$13$$$,因为有两个子数组的总和为 $$$13$$$($$$[3, 5, 5]$$$ 和 $$$[5, 5, 3]$$$),但 $$$13$$$ 仅在输入中出现一次。