← 返回题目列表

Codeforces · 1624/C

C. 除以二和排列

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。您可以对其进行操作。

在一次操作中,您可以将数组 $$$a_i$$$ 的任何元素替换为 $$$\lfloor \frac{a_i}{2} \rfloor$$$,即 $$$a_i$$$ 除以 $$$2$$$ 的整数部分(向下舍入)。

看看是否可以多次应用该操作(可能是 $$$0$$$)以使数组 $$$a$$$ 成为从 $$$1$$$ 到 $$$n$$$ 的数字排列 - 也就是说,它包含从 $$$1$$$ 到 $$$n$$$ 的所有数字,每个数字恰好一次。

例如,如果 $$$a = [1, 8, 25, 2]$$$, $$$n = 4$$$,那么答案是肯定的。您可以执行以下操作:

1. 将 $$$8$$$ 替换为 $$$\lfloor \frac{8}{2} \rfloor = 4$$$,则 $$$a = [1, 4, 25, 2]$$$。
2. 将 $$$25$$$ 替换为 $$$\lfloor \frac{25}{2} \rfloor = 12$$$,然后 $$$a = [1, 4, 12, 2]$$$。
3. 将 $$$12$$$ 替换为 $$$\lfloor \frac{12}{2} \rfloor = 6$$$,然后 $$$a = [1, 4, 6, 2]$$$。
4. 将 $$$6$$$ 替换为 $$$\lfloor \frac{6}{2} \rfloor = 3$$$,然后 $$$a = [1, 4, 3, 2]$$$。

输入

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

每个测试用例恰好包含两行。第一个包含整数 $$$n$$$ ($$$1 \le n \le 50$$$),第二个包含整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

对于每个测试用例,在单独的行上输出:

- 是,如果你可以使数组 $$$a$$$ 成为从 $$$1$$$ 到 $$$n$$$ 的数字排列,
- 否则不。

在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。

示例

输入 #1

6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22

输出 #1

YES
NO
YES
NO
NO
YES

注意

第一个测试用例在问题陈述的文本中进行了解释。

在第二个测试用例中,不可能获得排列。