English · Original
Chinese · Translation
Formal · Original
Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:
Find _k_ integers such that the sum of two to the power of each number equals to the number _n_ and the largest integer in the answer is as small as possible. As there may be multiple answers, you are asked to output the lexicographically largest one.
To be more clear, consider all integer sequence with length _k_ (_a_1, _a_2, ..., _a__k_) with . Give a value to each sequence. Among all sequence(s) that have the minimum _y_ value, output the one that is the lexicographically largest.
For definitions of powers and lexicographical order see notes.
## Input
The first line consists of two integers _n_ and _k_ (1 ≤ _n_ ≤ 1018, 1 ≤ _k_ ≤ 105) — the required sum and the length of the sequence.
## Output
Output "_No_" (without quotes) in a single line if there does not exist such sequence. Otherwise, output "_Yes_" (without quotes) in the first line, and _k_ numbers separated by space in the second line — the required sequence.
It is guaranteed that the integers in the answer sequence fit the range \[ - 1018, 1018\].
[samples]
## Note
**Sample 1:**
23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23
Answers like (3, 3, 2, 0, 1) or (0, 1, 2, 3, 3) are not lexicographically largest.
Answers like (4, 1, 1, 1, 0) do not have the minimum _y_ value.
**Sample 2:**
It can be shown there does not exist a sequence with length 2.
**Sample 3:**
**Powers of 2:**
If _x_ > 0, then 2_x_ = 2·2·2·...·2 (_x_ times).
If _x_ = 0, then 2_x_ = 1.
If _x_ < 0, then .
**Lexicographical order:**
Given two different sequences of the same length, (_a_1, _a_2, ... , _a__k_) and (_b_1, _b_2, ... , _b__k_), the first one is smaller than the second one for the lexicographical order, if and only if _a__i_ < _b__i_, for the first _i_ where _a__i_ and _b__i_ differ.
Jamie 正在准备一场 Codeforces 比赛。他想到了一个问题，但不知道如何解决。请帮他写出以下问题的解决方案：
找出 #cf_span[k] 个整数，使得每个数的 2 的幂次之和等于 #cf_span[n]，且答案中最大的整数尽可能小。如果有多个答案，请输出字典序最大的那个。
更明确地说，考虑所有长度为 #cf_span[k] 的整数序列 #cf_span[(a1, a2, ..., ak)]，满足 。为每个序列赋予一个值 。在所有具有最小 #cf_span[y] 值的序列中，输出字典序最大的那个。
关于幂和字典序的定义，请参见注释。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 1018, 1 ≤ k ≤ 105)] —— 所需的和与序列长度。
如果不存在这样的序列，请在一行中输出 "_No_"（不含引号）。否则，第一行输出 "_Yes_"（不含引号），第二行输出 #cf_span[k] 个用空格分隔的数 —— 所需的序列。
保证答案序列中的整数在范围 #cf_span[[ - 1018, 1018]] 内。
*样例 1:*
#cf_span[23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23]
像 #cf_span[(3, 3, 2, 0, 1)] 或 #cf_span[(0, 1, 2, 3, 3)] 这样的答案不是字典序最大的。
像 #cf_span[(4, 1, 1, 1, 0)] 这样的答案没有最小的 #cf_span[y] 值。
*样例 2:*
可以证明不存在长度为 2 的序列。
*样例 3:*
*2 的幂：*
如果 #cf_span[x > 0]，则 #cf_span[2x = 2·2·2·...·2]（共 #cf_span[x] 个 2）。
如果 #cf_span[x = 0]，则 #cf_span[2x = 1]。
如果 #cf_span[x < 0]，则 。
*字典序：*
对于两个长度相同的不同序列 #cf_span[(a1, a2, ... , ak)] 和 #cf_span[(b1, b2, ... , bk)]，如果在第一个满足 #cf_span[ai ≠ bi] 的位置 #cf_span[i] 上有 #cf_span[ai < bi]，则第一个序列在字典序上小于第二个序列。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 1018, 1 ≤ k ≤ 105)] —— 所需的和与序列长度。
## Output
如果不存在这样的序列，请在一行中输出 "_No_"（不含引号）。否则，第一行输出 "_Yes_"（不含引号），第二行输出 #cf_span[k] 个用空格分隔的数 —— 所需的序列。保证答案序列中的整数在范围 #cf_span[[ - 1018, 1018]] 内。
[samples]
## Note
*样例 1:* #cf_span[23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23]
像 #cf_span[(3, 3, 2, 0, 1)] 或 #cf_span[(0, 1, 2, 3, 3)] 这样的答案不是字典序最大的。
像 #cf_span[(4, 1, 1, 1, 0)] 这样的答案没有最小的 #cf_span[y] 值。
*样例 2:*
可以证明不存在长度为 2 的序列。
*样例 3:*
*2 的幂：*
如果 #cf_span[x > 0]，则 #cf_span[2x = 2·2·2·...·2]（共 #cf_span[x] 个 2）。
如果 #cf_span[x = 0]，则 #cf_span[2x = 1]。
如果 #cf_span[x < 0]，则 。
*字典序：*
对于两个长度相同的不同序列 #cf_span[(a1, a2, ... , ak)] 和 #cf_span[(b1, b2, ... , bk)]，如果在第一个满足 #cf_span[ai ≠ bi] 的位置 #cf_span[i] 上有 #cf_span[ai < bi]，则第一个序列在字典序上小于第二个序列。
Given integers $ n $ and $ k $, find a sequence $ (a_1, a_2, \dots, a_k) $ of integers such that:
$$
\sum_{i=1}^k 2^{a_i} = n
$$
and among all such sequences:
1. The maximum value $ \max_i a_i $ is minimized.
2. Among all sequences achieving this minimum maximum, the lexicographically largest sequence is selected.
If no such sequence exists, output "_No_". Otherwise, output "_Yes_" followed by the sequence.
---
**Formal Mathematical Statement:**
Let $ \mathcal{A} = \left\{ (a_1, \dots, a_k) \in \mathbb{Z}^k \mid \sum_{i=1}^k 2^{a_i} = n \right\} $.
Define $ y(a) = \max_{1 \leq i \leq k} a_i $.
Let $ y^* = \min_{a \in \mathcal{A}} y(a) $.
Let $ \mathcal{A}^* = \left\{ a \in \mathcal{A} \mid y(a) = y^* \right\} $.
Find $ a^* \in \mathcal{A}^* $ such that $ a^* $ is lexicographically largest among all elements of $ \mathcal{A}^* $.
If $ \mathcal{A} = \emptyset $, output "_No_".
Otherwise, output "_Yes_" and the sequence $ a^* $.
API Response (JSON)
{
"problem": {
"name": "B. Jamie and Binary Sequence (changed after round)",
"description": {
"content": "Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem: Find _k_ integers such that the sum of ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF916B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:\n\nFind _k_ integers such that the sum of ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Jamie 正在准备一场 Codeforces 比赛。他想到了一个问题，但不知道如何解决。请帮他写出以下问题的解决方案：\n\n找出 #cf_span[k] 个整数，使得每个数的 2 的幂次之和等于 #cf_span[n]，且答案中最大的整数尽可能小。如果有多个答案，请输出字典序最大的那个。\n\n更明确地说，考虑所有长度为 #cf_span[k] 的整数序列 #cf_span[(a1, a2, ...,...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given integers $ n $ and $ k $, find a sequence $ (a_1, a_2, \\dots, a_k) $ of integers such that:\n\n$$\n\\sum_{i=1}^k 2^{a_i} = n\n$$\n\nand among all such sequences:\n\n1. The maximum value $ \\max_i a_i $ is...",
"is_translate": false,
"language": "Formal"
}
]
}