305068: CF960C. Subsequence Counting

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Subsequence Counting

题意翻译

皮卡丘和他排成一列。他在纸上写下了数组的所有非空子序列。同时他删除了所有的「子序列的最大元素-子序列的最小元素 $\geq d$」的子序列,最终剩下 $X$ 个子序列。现在给出 $X,d$ ,构造一个合法的原序列。 输出数组中的元素数不应大于 $10^4$,数值大小不应超过 $10^{18}$ 。保证 $1\leq X,d\leq 10^9$ 。 translated by @皎月半洒花。

题目描述

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 $ 2^{n}-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 $ 10^{18} $ . Note the number of elements in the output array should not be more than $ 10^{4} $ . If no answer is possible, print $ -1 $ .

输入输出格式

输入格式


The only line of input consists of two space separated integers $ X $ and $ d $ ( $ 1<=X,d<=10^{9} $ ).

输出格式


Output should consist of two lines. First line should contain a single integer $ n $ ( $ 1<=n<=10000 $ )— the number of integers in the final array. Second line should consist of $ n $ space separated integers — $ a_{1},a_{2},...\ ,a_{n} $ ( $ 1<=a_{i}<10^{18} $ ). If there is no answer, print a single integer -1. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

10 5

输出样例 #1

6
5 50 7 15 6 100

输入样例 #2

4 2

输出样例 #2

4
10 100 1000 10000

说明

In the output of the first example case, the remaining subsequences after removing those with Maximum\_element\_of\_the\_subsequence $ - $ Minimum\_element\_of\_subsequence $ >=5 $ are $ [5],[5,7],[5,6],[5,7,6],[50],[7],[7,6],[15],[6],[100] $ . There are $ 10 $ of them. Hence, the array $ [5,50,7,15,6,100] $ is valid. Similarly, in the output of the second example case, the remaining sub-sequences after removing those with Maximum\_element\_of\_the\_subsequence $ - $ Minimum\_element\_of\_subsequence $ >=2 $ are $ [10],[100],[1000],[10000] $ . There are $ 4 $ of them. Hence, the array $ [10,100,1000,10000] $ is valid.

Input

题意翻译

皮卡丘和他排成一列。他在纸上写下了数组的所有非空子序列。同时他删除了所有的「子序列的最大元素-子序列的最小元素 $\geq d$」的子序列,最终剩下 $X$ 个子序列。现在给出 $X,d$ ,构造一个合法的原序列。 输出数组中的元素数不应大于 $10^4$,数值大小不应超过 $10^{18}$ 。保证 $1\leq X,d\leq 10^9$ 。 translated by @皎月半洒花。

加入题单

上一题 下一题 算法标签: