codeforces-scrape

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

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.