Codeforces Round #529 (Div.3)- Bài 3

Bài 3: 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,...,16$.
You are given two positive integers $n$ and $k$. Your task is to represent $n$ as the sum of exactly $k$ powers of two.
Input
The only line of input contains two integers $n$ and $k(1\le n\le 10^9,1\le k\le 2.10^5)$.
Output
If it is impossible to represented $n$ as the sum of $k$ powers of two, print "NO"
Otherwise, print "YES", and then print $k$ positive integers $b_1,b_2,...,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.

Examples

input

Copy

9 4

output

Copy

YES
1 2 2 4 

input

Copy

8 1

output

Copy

YES
8 

input

Copy

5 1

output

Copy

NO

input

Copy

3 7

output

Copy

NO

Solution:

#include <bits/stdc++.h>
using namespace std;
int a[200001], n, m, k;
int main() {
 scanf("%d%d", &n, &k);
 if(__builtin_popcount(n)>k || n<k)
  return 0*puts("NO");
 for(int i=30; i>=0; i--)
  while(n && k && (n-(1<<i))>=k-1) {
   n-=1<<i;
   k--;
   a[m++]=1<<i;
  }
 puts("YES");
 while(m--) printf("%d ", a[m]);
}