TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

97.2% (106/109)

Submission's AC Ratio

59.9% (145/242)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5