CF 1095C Powers Of Two

题目连接：http://codeforces.com/problemset/problem/1095/C

题目：

C. Powers Of Two

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A positive integer xx is called a power of two if it can be represented as x=2yx=2y, where yy is a non-negative integer. So, the powers of twoare 1,2,4,8,16,…1,2,4,8,16,….

You are given two positive integers nn and kk. Your task is to represent nn as the sum of exactly kk powers of two.

Input

The only line of the input contains two integers nn and kk (1≤n≤1091≤n≤109, 1≤k≤2⋅1051≤k≤2⋅105).

Output

If it is impossible to represent nn as the sum of kk powers of two, print NO.

Otherwise, print YES, and then print kk positive integers b1,b2,…,bkb1,b2,…,bk such that each of bibi is a power of two, and ∑i=1kbi=n∑i=1kbi=n. If there are multiple answers, you may print any of them.

Examples

Input

9 4

Output

YES

1 2 2 4

Input

8 1

Output

YES

8

Input

5 1

Output

NO

Input

3 7

Output

NO

题意：给出n,k,求出一个长度为k的2的幂的数列,使得 $\sum_{i=1}^na[i]=n%u2211 i=1 n %u200B a[i]=n$

思路：看到对于2的指数形式，首先要想到其中一个方法——将该数字换算成2进制。

该题正好可以。接着从最高位一步一步拆（03101001 sum=6 → 02301001 sum=7 → 01501001 sum=8）

代码中有更为详细的注解。

#include<stdio.h>

#include<iostream>

#include<algorithm>

using namespace std;

int n,k;

int s[105];//储存二进制数，且储存方式为低位在前，高位在后；

int main()

{

    scanf("%d %d",&n,&k);

    int x=n,sum=0;

    int t;//记录转换为二进制数的位数

    for(t=0;x!=0;)

    {

        s[++t]=x&1;

        x/=2;

        if(s[t])

            sum+=1;//记录二进制数中1的个数

    }

    /*开始写的时候在考虑 转换成二进制要进行拆分几次？如何判断？

    下面的循环体 就是判断条件 sum<k时肯定不符合题意，从最高位

    一次一次拆分，直到1的个数等于或大于k跳出循环体*/

    while(sum<k)

    {

        if(t==1)

            break;

        /*从最高位开始拆分，最高位-1，次高位加2，

        如果一直不能跳出循环，则换算成的二进制经过拆分，

        又回到了初始情况n，此时位数t为1，跳出循环*/

        s[t]-=1; s[t-1]+=2;

        if(!s[t])

            t-=1;

        sum+=1;

    }

    if(sum!=k)

    {

        puts("NO");return 0;

    }

    else

    {

        puts("YES");

        int T=1;

        for(int i=1;i<t;i++,T*=2)

        {

            for(int j=1;j<=s[i];j++)

                printf("%d ",T);

        }

        for(int i=1;i<s[t];i++)

            printf("%d ",T);

        printf("%d\n",T);

        return 0;

    }

}

巴特西

CF 1095C Powers Of Two

最新文章

热门文章