题目
https://codeforces.com/problemset/problem/1095/C
输入 n(1≤n≤1e9) k(1≤k≤2e5)。
把 n 分解为 k 个正整数,要求这些数都是 pow(2,i),即 1,2,4,8,……
如果无法做到,输出 NO,否则输出 YES 和这 k 个数。
输入
9 4
输出
YES
1 2 2 4
输入
8 1
输出
YES
8
输入
5 1
输出
NO
输入
3 7
输出
NO
Solution
难点在于如何输出这些数。一个方法是抓住一个数,除以2,然后append一个同样的数。另一个方法是创建k个1的数组然后将剩下的数直接分配过去。
def count_bit(n):
ans = 0
while n:
if n&1: ans += 1
n >>= 1
return ans
n, k = list(map(int, input().split()))
b = count_bit(n)
if k < b or k > n:
print('NO')
else:
print('YES')
ans = [1] * k
diff = n - k
for i in range(k):
while ans[i] <= diff:
diff -= ans[i]
ans[i] <<= 1
print(" ".join(map(str, ans)))