TopCoder

User's AC Ratio

96.1% (908/945)

Submission's AC Ratio

68.0% (1229/1807)

Tags

Description

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

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

1,3,5,,2i1,,2n3,2n1 (接1)

  將其重新編號,則編號為 1n 為成一圈與上述所剩下的人其號碼的對應方式為 i2i1

1,2,3,,i,,n1,n (接1)

Input Format

一個正整數 n (1n50)

Output Format

輸出 f(n) 之值。

Sample Input 1

41

Sample Output 1

19

Hints

Problem Source

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

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