codeforces-scrape

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

1221A.md (2129B)


      1 Source: https://codeforces.com/problemset/problem/1221/A
      2 
      3 A. 2048 Game
      4 
      5 time limit per test
      6 
      7 1 second
      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 playing a variation of game 2048. Initially you have a multiset $s$ of $n$ integers. Every integer in this multiset is a power of two.
     22 
     23 You may perform any number (possibly, zero) operations with this multiset.
     24 
     25 During each operation you choose two equal integers from $s$, remove them from $s$ and insert the number equal to their sum into $s$.
     26 
     27 For example, if $s = \{1, 2, 1, 1, 4, 2, 2\}$ and you choose integers $2$ and $2$, then the multiset becomes $\{1, 1, 1, 4, 4, 2\}$.
     28 
     29 You win if the number $2048$ belongs to your multiset. For example, if $s = \{1024, 512, 512, 4\}$ you can win as follows: choose $512$ and $512$, your multiset turns into $\{1024, 1024, 4\}$. Then choose $1024$ and $1024$, your multiset turns into $\{2048, 4\}$ and you win.
     30 
     31 You have to determine if you can win this game.
     32 
     33 You have to answer $q$ independent queries.
     34 
     35 Input
     36 
     37 The first line contains one integer $q$ ($1 \le q \le 100$) – the number of queries.
     38 
     39 The first line of each query contains one integer $n$ ($1 \le n \le 100$) — the number of elements in multiset.
     40 
     41 The second line of each query contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 2^{29}$) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.
     42 
     43 Output
     44 
     45 For each query print YES if it is possible to obtain the number $2048$ in your multiset, and NO otherwise.
     46 
     47 You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 6
     55 4
     56 1024 512 64 512
     57 1
     58 2048
     59 3
     60 64 512 2
     61 2
     62 4096 4
     63 7
     64 2048 2 2048 2048 2048 2048 2048
     65 2
     66 2048 4096
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 YES
     73 YES
     74 NO
     75 NO
     76 YES
     77 YES
     78 ```
     79 
     80 Note
     81 
     82 In the first query you can win as follows: choose $512$ and $512$, and $s$ turns into $\{1024, 64, 1024\}$. Then choose $1024$ and $1024$, and $s$ turns into $\{2048, 64\}$ and you win.
     83 
     84 In the second query $s$ contains $2048$ initially.