回分類題庫
d005: 2006 程式達人 D - 殺人遊戲
出處:

Difficulity : 2
Accepted : 60 Times | Submit :315 Times | Clicks : 6187
Accepted : 44 Users | Submit : 79 Users | Accepted rate : 56%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-09 00:01

Content :

所謂的殺人遊戲即有名的Joseph’s Problem。但有些人還不清楚,這裡解釋一下原來的問題:有 n 個人(編號從 1, 2, ..., 一直到 n)圍成一個圓圈站著。這些人每數 m 個人就要被殺掉一個,剩下最後一個人則被放走。 Joseph 很聰明懂得選最後被算到的位置,而逃過一劫。譬如當 n = 6m = 5 時,編號 5, 4, 6, 2, 3 號的人依序被殺掉,1 號則撿回一條命。

假設現在有 k 個好人跟 k 個壞人。在圓圈中編號前 k 個人是好人,後 k 個人是壞人。我們打算殺掉這其中一半的人,你得求出最小的 m 值,讓所有被殺死的人都是壞人。

Input :

輸入檔是一行一個數字 k。最後一行是 0。你可以假定 0 < k < 15

Output :

輸出也是一行一個數字,印出輸入檔 k 所對應的 m 值。

Sample Input :

3
4
0

Sample Output :

5
30

Hint :

解題率:5/22
Josephus problem
題目原出處:ACMOJ 305

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (0)

C++
C
JAVA
7143. derching (2 ms , 228KB)
53656. alun0922 (4 ms , 372KB)
61375. azoocz (6 ms , 374KB)
20821. liouzhou_101 (6 ms , 234KB)
61377. azoocz (8 ms , 368KB)
42697. cp100703009 (2 ms , 224KB)
32457. nothinglo (2 ms , 216KB)
20822. liouzhou_101 (2 ms , 238KB)
7144. derching (2 ms , 236KB)
4778. onedie (2 ms , 236KB)
90525. boy330077 (110 ms , 904KB)
63593. sky820902 (172 ms , 3008KB)
63592. sky820902 (416 ms , 3188KB)
90936. nwgs524513cja (990 ms , 1990KB)
76180. ag100j ( 1.2 s , 2168KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡