A11498 | Jamie and Binary Sequence (changed after round)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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.
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.
输入格式
The first line consists of two integers $n$ and $k$ ( $1<=n<=10^{18},1<=k<=10^{5})$ — the required sum and the length of the sequence.
输出格式
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 $[-10^{18},10^{18}]$ .
It is guaranteed that the integers in the answer sequence fit the range $[-10^{18},10^{18}]$ .
输入输出样例
输入 #1
23 5
输出 #1
Yes 3 3 2 1 0
输入 #2
13 2
输出 #2
No
输入 #3
1 2
输出 #3
Yes -1 -1
Sample 1:
$2^{3}+2^{3}+2^{2}+2^{1}+2^{0}=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.
$2^{3}+2^{3}+2^{2}+2^{1}+2^{0}=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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted