2013年7月6日 星期六

10774 - Repeated Josephus

Repeated Josephus
Input: standard input
Output: standard output
Time Limit: 1 second

不,我不希望你浪費重要的時間讀無聊的題目介紹。

首先,這有 個人,編號 1 到 n  並且圍成一圈。每隔一秒,將會保留一個人,並且殺掉下一個人,然後往下一個存活的人開始數,最後將只會有一個存活者。讓 x 為存活者的個數,而遊戲開始時,會有 x 個人,而最後的存活者編號為 y,而下一回合將會由 y 個人的遊戲繼續開始,直到存活者的編號不是原本最後一個編號。

例如:
n = 5,編號 1 2 3 4 5 繞成一圈,
第一回合依序殺掉 2 4 1 5,最後存活編號為 3。
接著,第二回合 n = 3,編號 1 2 3 繞成一圈,依序殺掉2 1,
因為 3 剛好是最後一個編號,遊戲結束。


Input

第一行有一個整數表示測資組數, 對於每組測資會有一個整數 n ( 0 < n ≤ 30000 ).


Output

對於每組測資,輸出測資組編號、回合次數及最後的存活者編號。
格式參考範例輸出。

Sample Input

2
13
23403

Sample Output

Case 1: 2 7
Case 2: 8 1023


Problem setter: Anupam Bhattacharjee, CSE, BUET
Thanks to Adrian for alternate solution.
 
"~~ Simple matters in the world need not always be simple ~~" 

沒有留言:

張貼留言