Pikachu had an array with him. He wrote down all the non-empty subsequences of the array on paper. Note that an array of size n has 2n - 1 non-empty subsequences in it.

Pikachu being mischievous as he always is, removed all the subsequences in which Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ d

Pikachu was finally left with X subsequences.

However, he lost the initial array he had, and now is in serious trouble. He still remembers the numbers X and d. He now wants you to construct any such array which will satisfy the above conditions. All the numbers in the final array should be positive integers less than 1018.

Note the number of elements in the output array should not be more than 104. If no answer is possible, print  - 1.

题目大意

有一个小伙砸弄出来一个集合,众所周知,集合的非空子集有2^n-1个
这个小伙砸把所以可能的子集中,集合最大值-集合最小值>=d的全部干掉
然后剩下X个集合
然后他不知道原来的集合了
所以要求构造一个长度不超过10000个元素的集合
x,d<=1e9
每个元素不大于1e18
输入 x,d
输出第一行 n表示构造出来的集合长度
接下来n个数字表示构造出来的集合


Examples
input
10 5
output
6
5 50 7 15 6 100

input
4 2
output
4
10 100 1000 10000


首先构造出来的集合,元素是可以重复的.
那考虑贪心一波
将x分成
2的幂次加和的形式
令nownum=随便一个数字
对于分解出来的每一个2的幂次
例如2^n,则你的集合中就应该有n个$$nownum$$
表示已经有$$2^n-1$$个子集满足要求了
然后让
$$x-=2^n-1$$
为了不影响已经构造出来的集合
每次分解的时候,都要让
$$nownum+=(2*d)$$(这个随意)

 

分类: 贪心题解

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒