codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.