1624C.md (2006B)
1 Source: https://codeforces.com/problemset/problem/1624/C 2 3 C. Division by Two and Permutation 4 5 time limit per test 6 7 3 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 You are given an array $a$ consisting of $n$ positive integers. You can perform operations on it. 22 23 In one operation you can replace any element of the array $a_i$ with $\lfloor \frac{a_i}{2} \rfloor$, that is, by an integer part of dividing $a_i$ by $2$ (rounding down). 24 25 See if you can apply the operation some number of times (possible $0$) to make the array $a$ become a permutation of numbers from $1$ to $n$ —that is, so that it contains all numbers from $1$ to $n$, each exactly once. 26 27 For example, if $a = [1, 8, 25, 2]$, $n = 4$, then the answer is yes. You could do the following: 28 29 1. Replace $8$ with $\lfloor \frac{8}{2} \rfloor = 4$, then $a = [1, 4, 25, 2]$. 30 2. Replace $25$ with $\lfloor \frac{25}{2} \rfloor = 12$, then $a = [1, 4, 12, 2]$. 31 3. Replace $12$ with $\lfloor \frac{12}{2} \rfloor = 6$, then $a = [1, 4, 6, 2]$. 32 4. Replace $6$ with $\lfloor \frac{6}{2} \rfloor = 3$, then $a = [1, 4, 3, 2]$. 33 34 Input 35 36 The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases. 37 38 Each test case contains exactly two lines. The first one contains an integer $n$ ($1 \le n \le 50$), the second one contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 39 40 Output 41 42 For each test case, output on a separate line: 43 44 * YES if you can make the array $a$ become a permutation of numbers from $1$ to $n$, 45 * NO otherwise. 46 47 You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response). 48 49 Example 50 51 Input 52 53 ``` 54 6 55 56 4 57 58 1 8 25 2 59 60 2 61 62 1 1 63 64 9 65 66 9 8 3 4 2 7 1 5 6 67 68 3 69 70 8 2 1 71 72 4 73 74 24 7 16 7 75 76 5 77 78 22 6 22 4 22 79 ``` 80 81 Output 82 83 ``` 84 YES 85 NO 86 YES 87 NO 88 NO 89 YES 90 ``` 91 92 Note 93 94 The first test case is explained in the text of the problem statement. 95 96 In the second test case, it is not possible to get a permutation.