← 返回题目列表

Codeforces · 1651/B

B. 证明他错了

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

最近,你的朋友发现了一个对整数数组 $$$a$$$ 的特殊操作:

1. 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$i \neq j$$$);
2. 设置 $$$a_i = a_j = |a_i - a_j|$$$。

这个操作玩了一会儿,他得出了下一个结论:

- 对于每个 $$$n$$$ 整数数组 $$$a$$$,其中 $$$1 \le a_i \le 10^9$$$,您可以找到一对索引 $$$(i, j)$$$,使得 $$$a$$$ 的总和在执行操作后会减少。

这个说法对你来说听起来很可疑,所以你想找到给定整数 $$$n$$$ 的反例。你能找到这样的反例并证明他错了吗?

换句话说,找到一个由 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) 组成的数组 $$$a$$$,这样对于所有索引对 $$$(i, j)$$$ 执行操作不会减少总和(它会增加或不会改变总和)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 数组 $$$a$$$ 的长度。

输出

对于每个测试用例,如果没有大小为 $$$n$$$ 的反例数组 $$$a$$$,则打印 NO。

否则,打印 YES 后跟数组 $$$a$$$ 本身 ($$$1 \le a_i \le 10^9$$$)。如果有多个反例,则打印任何一个。

示例

输入 #1

3
2
512
3

输出 #1

YES
1 337
NO
YES
31 4 159

注意

在第一个测试用例中,唯一可能的索引对是 $$$(1, 2)$$$ 和 $$$(2, 1)$$$。

如果您对索引 $$$(1, 2)$$$ (或 $$$(2, 1)$$$)执行操作,您将得到 $$$a_1 = a_2 = |1 - 337| = 336$$$,或数组$$$[336, 336]$$$。在这两种情况下,总和都会增加,因此这个数组 $$$a$$$ 是一个反例。