TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

83.7% (36/43)

Submission's AC Ratio

52.5% (74/141)

Tags

Description

「在視覺上,樹給我的享受是一種繁複的影像,不得不專注地停下腳步,用心靈仔細地分析。時常,我的智慧也無法精確地解析枝葉間華麗繁複的構造組織。她們在美的藝術造境上絕對嘆為觀止,變化萬千。」

──王家祥《遇見一株樹》

在這裡,我們只討論一種很特別,而且是最方便的樹:二元樹。
從前一題當中大家應該已經知道什麼樣子的樹會是一棵二元樹了!所謂的二元樹,顧名思義就是對於所有節點(node)來說,其子樹皆不超過兩棵。當然有的時候我們會依照性質把這兩棵樹劃分為左子樹以及右子樹。

當然,二元樹的功用不只是畫出來覺得很漂亮而已,二元樹多半具有分類的功能。
例如,一棵二元樹當中,若任何的左子樹根的數值不大於該節點的數值,並且該節點的數值也不大於右子樹樹根的樹值,那麼這棵樹就是一棵二元搜尋樹(Binary Search Tree)。

現在問題來了,要把數字 1,2,...,N 表示成一棵二元搜尋樹,有多少種表示方法呢?
例如N=3的時候,1,2,3所排列出合法的二元搜尋樹只可能是

這五種。
由於答案可能很大,請你只要輸出答案的科學記號表示法就可以了!

Input Format

輸入檔當中可能包含多筆測試資料,每一列有一個正整數N (1<=N<=1,000,000)。當N=0時代表輸入結束。

Output Format

對於每一筆測試資料請以科學記號表示輸出所求數字,數值部分請四捨五入至小數第三位輸出。

Sample Input 1

1
2
3
4
0

Sample Output 1

1.000E+0
2.000E+0
5.000E+0
1.400E+1

Hints

Problem Source

原TIOJ1107 / Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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