U28030.神奇的二进制
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
k 对于每日的进餐十分苛刻,需要精确到多少粒米,它坚信只有这样才能保持良好的身材。
但是每天管家很是头疼,他需要一粒一粒地数出来,为了解决这个问题,管家决定制作一台分发米粒的仪器,预先将米粒数量分配出来,装入每一碗(管家不想每次重新设置米粒数量,而是直接拿取仪器产生的每碗米粒,只要相加起来刚好等于 k 所需的米粒数即可)。
注意,每次只能启动一次仪器,仪器会按照每碗的米粒数量进行分配。
管家希望能够用最少碗数量来满足 k 所需 0 ~ n 粒米的任何数量,请不要浪费米粒,不需要凑成超过 n 粒米的数量。
输入格式
一个整数 n,表示 k 最大需要 n 粒米。
- 1≤n≤2147483647
输出格式
从小到大的顺序,依次输出每碗米粒的数量。
方案可以证明是唯一一种,能够对于任何 0 ~ n 粒米,碗的总数量最少、相同碗内米粒数量最少、所有碗内总米数不超过 n。
输入输出样例
输入#1
5
输出#1
1 2 2
输入#2
7
输出#2
1 2 4
说明/提示
-
样例一解释:只需要设置 3 碗数量,每碗内米粒数量是 1,2,3。
这样 0 ~ 5 粒米都可以从这 3 种碗任取得到。
-
样例二解释:
取 5 粒米的方法,第一碗和第三碗。
取 6 粒米的方法,第二碗和第三碗。
取 7 粒米的方法,取走全部的碗。