TopCoder

User's AC Ratio

91.0% (61/67)

Submission's AC Ratio

68.9% (93/135)

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 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

Hints

Problem Source

經典問題 / uva11351 The Last Man Standing

Subtasks

No. Testdata Range Score
1 0 5
2 1~2 15
3 3~4 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 2
3 1000 65536 262144 3
4 1000 65536 262144 3