Responsive image

问题 2619 --集合之和

2619: 集合之和

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

对于任意有限数集 A, B,定义二者之和 A + B 为:

例如,当 A = {1, 2}, B = {3, 4},有 A+B = {4, 5, 6}。注意此处并非可重集,因此即使 1+4 = 2+3 = 5,A + B 也仅包含一个 5。
记有限数集 A 中的元素个数为 |A|。
现给定 n,试构造数集 A 满足 |A + A| = n,且 A 中任一元素 x 满足 0 ≤ x ≤ 5 × 105 且 x 为整数。若有多个可行的 A,输出任意解均可。若 A 不存在,输出 −1。

输入描述

一行,一个正整数 n(1 ≤ n ≤ 5 × 105)。

输出描述

若 A 存在,第一行输出一个整数 |A|,表示集合 A 的元素个数。第二行输出 |A| 个互不相同的非负整数,表示 A 中的元素。
若 A 不存在,输出 −1。

样例输入

3

样例输出

2
114 514

提示


可以证明当 A = {114, 514},有 A + A = {228, 628, 1028},可见 |A + A| = 3。

来源

[提交][状态]
ACM算法攻关部