2011-08-23 15:11:12Morris
d228. kill man
d228. kill man
內容 ：
有 n 個人圍成一個圓圈等待處決。從第一個人開始跳過 k – 1 個人，第 k 個人被處決。然後再跳過 k – 1 個人，第 k 個人又被處決。淘汰的程序繞著圓圈進行，(隨著被處決的人的移除，圓圈會越變越小)，直到最後只剩一個人為止。
已知圓圈中的人數及 k。你必須找第m個被殺掉的人的號碼。
輸入說明
：
第一行有一個整數 t (0< t <=15)，代表有幾組測試資料。接下來的 t 行每行有三個整數n (0 < n <= 70000) , k (0 < k <= 109) ,m (0 < m <= n) . n >10000 t會小於5組
輸出說明
：
每組測試的輸出格式為 "Case i: a"，其中 "i" 為測資編號，"a" 則為圓圈中倖存的人 (請參考範例)。
範例輸入 ：
4 6 3 3 8 6 6 11 99 11 23 13 23
範例輸出 ：
Case 1: 4 Case 2: 7 Case 3: 5 Case 4: 12
提示
：
出處
：
/**********************************************************************************/
/* Problem: d228 "kill man" from */
/* Language: C */
/* Result: AC (20ms, 765KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-23 15:06:19 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int C[70001] = {}, LOW[70001];
int Modify (int N, int L) {
while(N <= L) {
C[N] += 1;
N += LOW[N];
}
}
int Operator (int N) {
int Sum = 0;
while(N) {
Sum += C[N];
N -= LOW[N];
}
return Sum;
}
main() {
int t, n, m, k, test = 0, a;
for(a = 0; a < 70001; a++) LOW[a] = a & (-a);
scanf("%d",&t);
while(t--) {
int a, Ans = 0;
scanf("%d %d %d", &n, &k, &m);
memset(C, 0, sizeof(C));
int kp = 0, skip, lave = n, tk, ttk;
if(n != m) {
for(a = 1; a <= m; a++) {
tk = k%lave;
if(tk == 0) tk = lave;
while(tk) {
if(kp + tk > n) {
skip = Operator(n) - Operator(kp);
ttk = tk, tk = tk - (n-kp-skip);
kp = 0;
}
else {
skip = Operator(kp+tk) - Operator(kp);
kp = kp + tk;
tk = skip;
if(skip == 0) break;
}
}
Modify(kp, n), lave--;
}
} else {
for(a = 2; a <= n; a++)
kp = (k+kp)%a;
kp++;
}
printf("Case %d: %d\n", ++test, kp);
}
return 0;
}
Recursive:
f[i] = (k - 1) % i when i == n + 1 - m
f[i] = (f[i - 1] + k) % i when i <= n
忘了補充
算完後的編號是 0 ~ n - 1 之下，調整只要加 1 就可。