1020 . F.Number Insertion
TopCoder
Tags
Description
有一個序列，一開始只有兩個數字(0,1)。接下來依序把2,3,4,...,n插入這個序列，將數字k插入序列的某個位置時必須保證與k相鄰的兩個數字和是k的一個因數。因為是「插入序列」，因此不能把新的數字放到序列的兩端，我們不妨將這樣的序列稱為「n-合法序列」。例如n=4的時候總共只有兩個「4-合法序列」(0,4,2,3,1)和(0,2,3,4,1)。
現在給你正整數 n，請你算算看有多少個不全相同的「n-合法序列」？
為了方便檢驗，請你也順便輸出一個字典順序最大的「n-合法序列」(如果存在這樣的序列的話)。
Input Format
每個輸入檔只包含一筆測試資料。只有一個正整數 $n(1 \leq n \leq 31)$。
<!--※Time Limit: 1.5 sec per input file-->
Output Format
Line 1: 請輸出一個整數代表「n-合法序列」的個數S。
Line 2: 請輸出字典順序最大的「n-合法序列」，若S等於0，請你不要輸出任何東西。
Sample Input 1
6
Sample Output 1
4
0 6 2 5 3 4 1
0 6 2 5 3 4 1
Hints
Mainly Use Search Techniques:)
<!--
註：
總共有五個測試檔。
最上面的Time Limit是指跑完五個測試檔案的總時間限制。
每個測試檔的時間限制為1.5秒。
-->
Problem Source
原TIOJ1020 / Problem Setter: Tmt
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |