d192: 11351 - Last Man Standing
Tags :
Accepted rate : 181人/220人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-23 18:45

Content

有 n 個人圍成一個圓圈等待處決。從第一個人開始跳過 k – 1 個人,第 k 個人被處決。然後再跳過 k – 1 個人,第 k 個人又被處決。淘汰的程序繞著圓圈進行,(隨著被處決的人的移除,圓圈會越變越小),直到最後只剩一個人為止。

已知圓圈中的人數及 k。你必須找最後倖存的人的號碼。

Input
第一行有一個整數 t (0< t <=100),代表有幾組測試資料。接下來的 t 行每行有兩個整數n (0 < n <= 105) 及 k (0 < k <= 109).。
Output
每組測試的輸出格式為 "Case i: a",其中 "i" 為測資編號,"a" 則為圓圈中倖存的人 (請參考範例)。
Sample Input #1
4
6 3
8 6
11 99
23 13
Sample Output #1
Case 1: 1
Case 2: 1
Case 3: 5
Case 4: 12
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
UVa 原題
Tags:
出處:
UVa11351 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」