TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

100.0% (34/34)

Submission's AC Ratio

69.0% (40/58)

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)$。

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:)

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