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 ```