TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

97.7% (42/43)

Submission's AC Ratio

64.0% (55/86)

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

6

Sample Output

4
0 6 2 5 3 4 1

Hints

Mainly Use Search Techniques:)
<!--
註:
總共有五個測試檔。
最上面的Time Limit是指跑完五個測試檔案的總時間限制。
每個測試檔的時間限制為1.5秒。
-->

Problem Source

原TIOJ1020 / Problem Setter: Tmt

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536