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
#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]); }
Không có nhận xét nào:
Đăng nhận xét