回『競賽題庫』
b551: 2. 羅馬羅盤
標籤 :

通過比率 : 26% (5 人 / 19 人 ) (非即時)
評分方式: Tolerant , 記憶體限制: 64 MB
公開 測資點 1 (20%): 1.0s , <1K
公開 測資點 2 (20%): 1.0s , <1K
公開 測資點 3 (20%): 1.0s , <1K
公開 測資點 4 (20%): 1.0s , <1K
公開 測資點 5 (20%): 1.0s , <1K
最近更新 : 2017-03-08 16:30

內容 :

問題描述
 西元 67 年,在羅馬和猶太人的衝突中史學家 約瑟夫 和其他 40 個人被關 在一個洞穴中。羅馬人知道 約瑟夫 的下落後希望他能投效羅馬帝國。但是同 伴們卻不允許他投降。所以 約瑟夫 建議他們彼此殺害,一個接一個,被的順序就由命運決定。傳統上他們決定命運的方式為:大家圍成一個圓圈,從某人開 始算起,每到 3個人那人就被殺掉,如此不斷下去直到只剩一個人。後來約瑟夫 成為唯一的存活者並投降羅馬。我們有興趣是: 約瑟夫如何剛好是那個 存活者?真的是運氣好,還他事先在暗地裡用 41 顆石頭練習過,或者他有一個數學的方法可以知道要站在哪一位置才能成為最後存活者?

 聽過這個故事後,你憂心要是將來某一天也面臨同樣的情況怎麼辦。所以決定用電腦寫一個程式算出應該從那人開始算起,你才可以成為最後唯一存活的人。

 在本問題中,你的程式必須解決約瑟夫情況的變形。有 n個人排成一圓圈,面向內,依順時鐘方向編號從 1到 n。你的位置在 1。殺人程序由編號 i的 人開始順時鐘方向算起,到第 k個人,那立刻被殺掉。然後 ,從被殺的人 左邊的人再順時鐘方向算 k個人,那必須負責埋葬剛才被殺的然後回去 站在剛才被殺的人位置。接下來從這個左邊的人算起,第 k個人又被殺掉, 如此一直下去直到只剩下一個人為止?

例如,當n=5、k=2、i=1,那麼被殺的順序為2、5、3、1,存活者為4,


以若往前倒移三個人,從第3個人開始數,存活者就是1

輸入說明 :

測試資料有t列(1≦t≦100),以EOF結束,每列 2個以空格 隔開的 整數 n和 k,1≦n≦100 、 1≦k≦10^9

輸出說明 :

對測試資料每列的兩個整數,一開始時應該從哪個人算起(也就是 i),才能確保你是唯一的存活者。

每列一個i值,如範例。

範例輸入 : help
若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5 2
7 3
範例輸出:
3
1
提示 :
標籤:
出處:
103學年度北二區桃竹苗基區資訊學科能力競賽 (管理:p3a_owhj)

本題狀況 本題討論 排行