1654C.md (2756B)
1 Source: https://codeforces.com/problemset/problem/1654/C 2 3 C. Alice and the Cake 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 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. 24 25 You are given the array $a$. Determine whether there exists an initial weight and sequence of operations which results in $a$. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$). 32 33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$). 34 35 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, print a single line: print YES if the array $a$ could have resulted from Alice's operations, otherwise print NO. 40 41 You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer). 42 43 Example 44 45 Input 46 47 ``` 48 14 49 50 1 51 52 327 53 54 2 55 56 869 541 57 58 2 59 60 985214736 985214737 61 62 3 63 64 2 3 1 65 66 3 67 68 2 3 3 69 70 6 71 72 1 1 1 1 1 1 73 74 6 75 76 100 100 100 100 100 100 77 78 8 79 80 100 100 100 100 100 100 100 100 81 82 8 83 84 2 16 1 8 64 1 4 32 85 86 10 87 88 1 2 4 7 1 1 1 1 7 2 89 90 10 91 92 7 1 1 1 3 1 3 3 2 3 93 94 10 95 96 1 4 4 1 1 1 3 3 3 1 97 98 10 99 100 2 3 2 2 1 2 2 2 2 2 101 102 4 103 104 999999999 999999999 999999999 999999999 105 ``` 106 107 Output 108 109 ``` 110 YES 111 NO 112 YES 113 YES 114 NO 115 YES 116 NO 117 YES 118 YES 119 YES 120 YES 121 NO 122 NO 123 YES 124 ``` 125 126 Note 127 128 In the first test case, it's possible to get the array $a$ by performing $0$ operations on a cake with weight $327$. 129 130 In the second test case, it's not possible to get the array $a$. 131 132 In the third test case, it's possible to get the array $a$ by performing $1$ operation on a cake with weight $1\,970\,429\,473$: 133 134 * Cut it in half, so that the weights are $[985\,214\,736, 985\,214\,737]$. 135 136 Note that the starting weight can be greater than $10^9$. 137 138 In the fourth test case, it's possible to get the array $a$ by performing $2$ operations on a cake with weight $6$: 139 140 * Cut it in half, so that the weights are $[3,3]$. 141 * Cut one of the two pieces with weight $3$, so that the new weights are $[1, 2, 3]$ which is equivalent to $[2, 3, 1]$ up to reordering.