← 返回题目列表

Codeforces · 1823/A

A. A 特性

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

考虑一个由数字 $$$1$$$ 和 $$$-1$$$ 组成的数组 $$$a_1, a_2, \dots, a_n$$$。将该数组的 $$$A$$$ 特征定义为多对索引 $$$1 \le i < j \le n$$$,使得 $$$a_i \cdot a_j = 1$$$。

查找任何具有给定长度 $$$n$$$ 且 $$$A$$$ 特征等于给定值 $$$k$$$ 的数组 $$$a$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 100$$$; $$$0 \le k \le \frac{(n-1) n}{2}$$$) - 所需数组的长度和所需的 $$$A$$$ 特性。

输出

对于每个测试用例,如果不存在具有给定 $$$A$$$ 特征 $$$k$$$ 的数组 $$$a$$$,则打印 NO。

否则,打印 YES 和 $$$n$$$ 数字 $$$1$$$ 和 $$$-1$$$,它们形成所需的数组 $$$a$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

7
2 0
2 1
3 1
3 2
3 3
5 4
5 5

输出 #1

YES
1 -1 
YES
1 1 
YES
1 -1 1 
NO
YES
1 1 1 
YES
-1 1 -1 1 1 
NO

注意

在第一个测试用例中,数组中只有一对不同的元素,它们的乘积为 $$$a_1 \cdot a_2 = -1 \neq 1$$$,因此其 $$$A$$$ 特征为 $$$0$$$。

在第二个测试用例中,数组中只有一对不同的元素,它们的乘积为 $$$a_1 \cdot a_2 = 1$$$,因此其 $$$A$$$ 特征为 $$$1$$$。

在第三个测试用例中,数组中有三对不同的元素,它们的乘积为:$$$a_1 \cdot a_2 = -1$$$、$$$a_1 \cdot a_3 = 1$$$、$$$a_2 \cdot a_3 = -1$$$,因此其$$$A$$$特征为$$$1$$$。

在第四个测试用例中,我们可以证明,不存在长度为 $$$3$$$ 的数组,其 $$$A$$$ 特征为 $$$2$$$。