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

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

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

【题目描述】

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

例如,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


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

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

分享给朋友:

相关文章

【题解】选班委

【题目描述】小 T 和他的小伙伴们到 CZ 中学的创新实验班报到后的第一件事就是选班委,班主任 R 老师走上讲台宣布了选举办法,首先让全班 40 位同学依次上讲台做自我介绍,然后按照 职位一个一个依次...

字符串反连接

【题目描述】写一函数,使输入的一个字符串按反序存放,在主函数中输入并输出反序后的字符串(不包含空格)。【输入描述】一行字符【输出描述】逆序后的字符串【样例输入】123456abcdef【样例输出】fe...

【题解】真分数(2019青岛市程序设计竞赛)

【描述】真分数,指的是分子比分母小的分数,真分数的分数值小于1。给出n个正整数,任取两个数分别作为分子和分母组成真分数。求能组成多少不同值的真分数。【输入】第一行是一个正整数n。第二行是n个不同的正整...

【循环】日记第几天

【题目描述】小明每天都坚持写日记,突然有一天小明在想,我今年写了多少篇日记了?一篇一篇的数好麻烦,没办法小明只能把这个艰难的问题交给聪明的你来解决。【输入描述】输入三个整数�y,m,d分别表示年月日,...

【题解】跳格子

【题目描述】地面上有一排长度为n的格子1-n,每个格子上都有一个数xi,开始时你在位置0,每次你可以向前跳1-2格,然后取走格子上的数,直到跳到位置n+1。取走的数的和就是你的得分,现在你想知道你可能...

【题解】移动路线

【题目描述】X桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。小明是个调皮的孩子,一...