TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

71.4% (30/42)

Tags

uva

Description

有$n$個人圍成一圈等著被處決,從第一個人開始,前$k-1$個人會被跳過,第$k$個人會被處決,如此不斷重複。當每個被處決的人被移出,這些人圍成的圈子會一次一次的愈來愈小。最後會剩下一個存活者,他將被稱為「最後仍站著的男♂人」。

Input Format

第一行有一個整數 $ 0 < m \leq 100 $
之後的$m$行 每行會有整數 $ 0 < n \leq 10^5 $ 與整數 $ 0 < k \leq 10^9 $.

Output Format

請依照此格式輸出「Case i: a」 其中i是代表第幾個輸出,a代表「最後仍站著的男♂人」的編號。

Sample Input

4
6 3
8 6
11 99
23 13

Sample Output

Case 1: 1
Case 2: 1
Case 3: 5
Case 4: 12

Hints

Problem Source

經典問題 / uva11351 The Last Man Standing

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 2, Score: 15
For Testdata: 3 ~ 4, Score: 80
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536