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

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

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

【题目描述】

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

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


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

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

分享给朋友:

相关文章

【题解】跳格子

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

【题解】画百钱买百鸡

【题目描述】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡。问鸡翁、鸡母、鸡雏各几何?#include<iostream> using namespace ...

【题解】大数取模

【题目描述】求m%n。【输入描述】两个数,m和n。【输出描述】m模n的值。【样例输入】3【样例输出】2【数据范围】对于30%的数据, 1<m<10^18对于70%的数据, m>10^...

【题解】母牛的故事

【题解】母牛的故事

【题目描述】有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?【输入描述】输入数据由多个测试实例组成,每个测试实例占一行...

【题解】最少操作使数组递增

【题目描述】给你一个整数数组 nums (下标从 0 开始)。每一次操作中,你可以选择数组中一个元素,并将它增加 1 。比方说,如果 nums = [...

【题解】苯小猴

【题目描述】笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn是单词中出现次数最...