← 返回题目

题库练习 Alice and the Cake

← 上一题下一题 →

A14903 | $Alice and the Cake$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Alice has a cake, and she is going to cut it. She will perform the following operation $n-1$ times: choose a piece of the cake (initially, the cake is all one piece) with weight $w\ge 2$ and cut it into two smaller pieces of weight $\lfloor\frac{w}{2}\rfloor$ and $\lceil\frac{w}{2}\rceil$ ( $\lfloor x \rfloor$ and $\lceil x \rceil$ denote [floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions), respectively). After cutting the cake in $n$ pieces, she will line up these $n$ pieces on a table in an arbitrary order. Let $a_i$ be the weight of the $i$ -th piece in the line. You are given the array $a$ . Determine whether there exists an initial weight and sequence of operations which results in $a$ .

输入格式

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The first line of each test case contains a single integer $n$ ( $1 \le n \le 2 \cdot 10^5$ ). The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ). It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$ .

输出格式

For each test case, print a single line: print YES if the array $a$ could have resulted from Alice's operations, otherwise print NO. You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

输入输出样例

输入 #1

14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999

输出 #1

YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES

C++ 编辑器

输入

输出