当前位置:首页 > 题解目录 > 正文内容

【题解】2020-T1 优秀的拆分

亿万年的星光5年前 (2021-10-04)题解目录2132

【题目描述】

一般来说,一个正整数可以拆分成若干个正整数的和。

例如,1=1,10=1+2+3+4等。对于正整数n的一种特定拆分,当且仅当在这种拆分下,n被分解为若干个不同的2的正整数次幂。

注意,一个数x能被表示成2的正整数次幂,当且仅当x能通过正整数个2相乘在一起得到。

 例如,10=8+2=2^3 +2^1 是一个优秀的拆分。但是,7=4+2+1=2^2+2^1+2^0就不是一个优秀的拆分,因为1不是2的正整数次幂。

 现在,给定正整数n,你需要判断这个数的所有拆分中,是否存在优秀的拆分,若存在,请给出具体的拆分方案。
【输入描述】

输入只有一行,一个整数n,代表需要判断的数。


【输出描述

如果这个数的所有拆分中,存在优秀的拆分。那么,你需要从大到小输出这个拆分中的每一个数,相邻两个数之间用一个空格隔开。可以证明,在规定了拆分数字的顺序后,该拆分方案是唯一的。

若不存在优秀的拆分,输出-1。

【样例输入】

6

【样例输出】

4 2

【提示】

样例解释

6=4+2=22+21是一个优秀的拆分。注意6=2+2+2不是一个优秀的拆分,因为拆分成的3个数不满足每个数互不相同。


【样例输入2】

7


【样例输出2】

-1

【数据规模与约定】

对于20%的数据,n<=10。

对于另外20%的数据,保证n为奇数。

对于另外20%的数据,保证n为2的正整数次幂。

对于80%的数据,n<=1024。

对于100%的数据,1<=n<=1*10^7


    扫描二维码推送至手机访问。

    版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

    分享给朋友:

    相关文章

    【题解】山区建小学

    【题目描述】政府在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数),其中,0<i<...

    【题解】变换数组

    【题目描述】输入一个数组 a,包含有 n 个元素 a1,a2,⋯,an。对这个数组进行 m 次变换,每次变换会将数组 a ...

    【题解】切割钢管

    【题解】切割钢管

    【题目描述】小A是某工地的计算工程师。工地现有 n 根钢管,第 i 根钢管的长度为 ai。现在想用这 n 根钢管来做一个支撑用的柱子。我么可以切割这些钢管成为更短的钢管,但是不能缝合两根钢管。为了安全...

    【题解】链表操作

    【题目描述】给定一个N个数的数组,M次操作,每次操作为下列操作之一。求最后的数组。操作1:在第X个数之后插入一个数Y。操作2:删除第X个数。操作3:对区间[X,Y]进行排序。操作4:对区间[X,Y]进...

    【题解】红与黑

    【题解】红与黑

    【题目描述】有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。【输入】包括多组数据。每...

    【题解】后缀表达式的值

    【题解】后缀表达式的值

    【题目描述】从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(+)、减(—)、乘(*)、除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标...