满足如下条件的序列X(序列中元素被标号为1、2、3…m)被称为“加成序列”:
X[1]=1
X[m]=n
X[1]<X[2]<…<X[m-1]<X[m]
对于每个 k(2≤k≤m) ( ) 都存在两个整数 i 和 j ( 1≤i , j≤k−1,i ( , 和 j 可相等 ) ) ,使得 X[k]=X[i]+X[j] 。
你的任务是:给定一个整数 n ,找出符合上述条件的长度 m 最小的 "加成序列"。
如果有多个满足要求的答案,只需要找出任意一个可行解。
输入包含多组测试用例。
每组测试用例占据一行,包含一个整数 n 。
当输入为单行的0时,表示输入结束。
对于每个测试用例,输出一个满足需求的整数序列,数字之间用空格隔开。
每个输出占一行。
5 7 12 15 77 0
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77
1≤n≤100
此题虽然没有 SPJ,但是加了一个 checker(By Laffey)程序可以用于本地测试。
checker 食用方式:
编译
将编译出的可执行文件移至程序输出所在目录下。
运行指令
./checker <test_file> <n> <m>
checker.exe <test_file> <n> <m>
其中尖括号括起内容根据实际情况替换。
如:我的程序将结果输出到了 ans.txt 中,该测试点输入数据为 20,我的程序求出数列长度为 10,则我应当运行指令 checker ans.txt 20 10。
ans.txt
20
10
checker ans.txt 20 10
附:checker 测试输出说明。
ok
A
B
C <a>
D <k>