TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

97.5% (693/711)

Submission's AC Ratio

70.7% (919/1300)

Description

電腦程式語言的架構中,遞迴函數可說是較特殊的一種,因函數可以呼叫函數本身自己。

請設計一個程式,用遞迴函數解決下面兩小題(Problem 1003, Problem 1004)。

設有一 16 吋義大利脆餅,今欲以刀切餅,每刀均以直線方式切於餅面,第一刀可將脆餅切成兩片,二刀至多可分成 4 片,三刀至多可分成 7 片,試問 $n$ 刀至多可將脆餅切成幾片?令 $f(n)$ 為 $n$ 刀將脆餅分成的片數,則 $f(0)=1$。

Input Format

一個正整數 $n$ $(1\le n \le 50)$。

Output Format

輸出 $f(n)$ 之值。

Sample Input

3

Sample Output

7

Hints

三條不交於一點的直線可將平面分成 7 份。

Problem Source

原TIOJ1003 / 建國中學95學年度校內資訊能力競賽(1, recursive-a)

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 (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