Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. unsigned long long P2[66],n,k,nr,x[200005],s,kk;
  6. bool found = true;
  7.  
  8. void GeneratePow2(){
  9.     for(int i = 0;i < 64;i++)
  10.         P2[i] = (1 << i);
  11. }
  12.  
  13. int BS(unsigned long long x){
  14.     int st  = 0,dr = 63;
  15.     while(st < dr){
  16.         int mid = (st + dr) / 2;
  17.         if(P2[mid] < x)
  18.             st = mid + 1;
  19.         else
  20.             dr = mid;
  21.     }
  22.     while(P2[st] > x)
  23.         st--;
  24.     return st;
  25. }
  26.  
  27. bool OK(int k){
  28.     s = 0;
  29.     if(x[k] < x[k - 1])
  30.         return false;
  31.     for(int i = 1;i <= k;i++)
  32.         s += x[i];
  33.     return (s <= nr);
  34. }
  35.  
  36. void Back(int k){
  37.     for(int i = 0;i <= n;i++){
  38.         x[k] = P2[i];
  39.         if(OK(k)){
  40.             if(s == nr && k == kk){
  41.                 found = false;
  42.                 cout << "YES" << "\n";
  43.                 for(int j = 1;j <= k;j++)
  44.                     cout << x[j] << " ";
  45.                 cout << "\n";
  46.                 return;
  47.             }else Back(k + 1);
  48.         }
  49.     }
  50. }
  51.  
  52. int main(){
  53.     GeneratePow2();
  54.     cin >> nr >> kk;
  55.     if(kk == 1)
  56.     {
  57.         if(!(nr & (nr - 1)))
  58.             cout << "YES\n" << nr;
  59.         else
  60.             cout << "NO";
  61.         return 0;
  62.     }
  63.     n = BS(nr);
  64.     Back(1);
  65.     if(found == true)
  66.         cout << "NO";
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement