TopCoder

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

User's AC Ratio

96.4% (264/274)

Submission's AC Ratio

65.1% (383/588)

Description

於第一世紀時,猶太人受制於羅馬帝國,一批愛國志士反叛羅馬帝國,最後僅剩下41人受困於山洞。這41人不想受辱於羅馬帝國,又不想自殺,因此決定圍成一個圓圈,由1號開始將2號殺掉;3號將4號殺掉,依此類推,即由前一個殺掉下一個,欲將全團41人全部殉戰而亡。然而,最後必定會剩下一人。試問哪一號最後得以苟且偷生?如果有n個人圍成一圓圈,誰得以殘留餘命呢?

  令 $f(n)$ 為最後留下性命的號數,則 $f(1)=1$。設有 $2n$ 個人,則過了第一圈後所有偶數號的都要被去除,剩下的人為成一圈如下:

$1, 3, 5, \cdots, 2i-1, \cdots, 2n-3, 2n-1$ (接1)

  將其重新編號,則編號為 $1$ 至 $n$ 為成一圈與上述所剩下的人其號碼的對應方式為 $i \rightarrow 2i-1$。

$1, 2, 3, \cdots, i, \cdots, n-1, n$ (接1)

Input Format

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

Output Format

輸出 $f(n)$ 之值。

Sample Input

41

Sample Output

19

Hints

Problem Source

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

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