codeforces-scrape

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

1095C.md (1104B)


      1 Source: https://codeforces.com/problemset/problem/1095/C
      2 
      3 C. Powers Of Two
      4 
      5 time limit per test
      6 
      7 4 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 A positive integer $x$ is called a power of two if it can be represented as $x = 2^y$, where $y$ is a non-negative integer. So, the powers of two are $1, 2, 4, 8, 16, \dots$.
     22 
     23 You are given two positive integers $n$ and $k$. Your task is to represent $n$ as the sum of exactly $k$ powers of two.
     24 
     25 Input
     26 
     27 The only line of the input contains two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 2 \cdot 10^5$).
     28 
     29 Output
     30 
     31 If it is impossible to represent $n$ as the sum of $k$ powers of two, print NO.
     32 
     33 Otherwise, print YES, and then print $k$ positive integers $b_1, b_2, \dots, b_k$ such that each of $b_i$ is a power of two, and $\sum \limits_{i = 1}^{k} b_i = n$. If there are multiple answers, you may print any of them.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 9 4
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 YES
     47 1 2 2 4
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 8 1
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 YES
     60 8
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 NO
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 3 7
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 NO
     85 ```