2548 問(wèn)題 B: [CSP-J2020] 優(yōu)秀的拆分
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 1305 解決: 549
題目描述
一般來(lái)說(shuō),一個(gè)正整數(shù)可以拆分成若干個(gè)正整數(shù)的和。例如,1 = 1,10 = 1 + 2 + 3 + 4 等。
對(duì)于正整數(shù) n 的一種特定拆分,我們稱它為“優(yōu)秀的”,當(dāng)且僅當(dāng)在這種拆 分下,n 被分解為了若干個(gè)不同的 2 的正整數(shù)次冪。注意,一個(gè)數(shù) x 能被表 示成 2 的正整數(shù)次冪,當(dāng)且僅當(dāng) x 能通過(guò)正整數(shù)個(gè) 2 相乘在一起得到。
例如,10 = 8 + 2 = 23 + 21 是一個(gè)優(yōu)秀的拆分。但是,7 = 4 + 2 + 1 = 22 + 21 + 20 就不是一個(gè)優(yōu)秀的拆分,因?yàn)?1 不是 2 的正整數(shù)次冪。
現(xiàn)在,給定正整數(shù) n,你需要判斷這個(gè)數(shù)的所有拆分中,是否存在優(yōu)秀的 拆分。若存在,請(qǐng)你給出具體的拆分方案。
輸入
輸入只有一行,一個(gè)正整數(shù) n,代表需要判斷的數(shù)。
輸出
如果這個(gè)數(shù)的所有拆分中,存在優(yōu)秀的拆分。那么,你需要從大到小輸出 這個(gè)拆分中的每一個(gè)數(shù),相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開。可以證明,在規(guī)定 了拆分?jǐn)?shù)字的順序后,該拆分方案是唯一的。 若不存在優(yōu)秀的拆分,輸出“-1”(不包含雙引號(hào))。
提示
對(duì)于 20% 的數(shù)據(jù),n ≤ 10。 對(duì)于另外 20% 的數(shù)據(jù),保證 n 為奇數(shù)。
對(duì)于另外 20% 的數(shù)據(jù),保證 n 為 2 的正整數(shù)次冪。
對(duì)于 80% 的數(shù)據(jù),n ≤ 1024。
對(duì)于 100% 的數(shù)據(jù),1 ≤ n ≤ 1 × 107。