U28030.神奇的二进制

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

kk 对于每日的进餐十分苛刻,需要精确到多少粒米,它坚信只有这样才能保持良好的身材。

但是每天管家很是头疼,他需要一粒一粒地数出来,为了解决这个问题,管家决定制作一台分发米粒的仪器,预先将米粒数量分配出来,装入每一碗(管家不想每次重新设置米粒数量,而是直接拿取仪器产生的每碗米粒,只要相加起来刚好等于 kk 所需的米粒数即可)。

注意,每次只能启动一次仪器,仪器会按照每碗的米粒数量进行分配。

管家希望能够用最少碗数量来满足 kk 所需 00 ~ nn 粒米的任何数量,请不要浪费米粒,不需要凑成超过 nn 粒米的数量。

输入格式

一个整数 nn,表示 kk 最大需要 nn 粒米。


  • 1n21474836471\leq n\leq 2147483647

输出格式

从小到大的顺序,依次输出每碗米粒的数量。

方案可以证明是唯一一种,能够对于任何 00 ~ nn 粒米,碗的总数量最少、相同碗内米粒数量最少、所有碗内总米数不超过 nn

输入输出样例

  • 输入#1

    5

    输出#1

    1 2 2
  • 输入#2

    7

    输出#2

    1 2 4

说明/提示

  • 样例一解释:只需要设置 33 碗数量,每碗内米粒数量是 1,2,31,2,3

    这样 00 ~ 55 粒米都可以从这 33 种碗任取得到。

  • 样例二解释:

    55 粒米的方法,第一碗和第三碗。

    66 粒米的方法,第二碗和第三碗。

    77 粒米的方法,取走全部的碗。

首页