2011-09-01 08:11:03Morris
c108. Joseph
c108. Joseph
作法 : 模擬+建表
/**********************************************************************************/
/* Problem: c108 "Joseph" from ACM 305 */
/* Language: C */
/* Result: AC (444ms, 228KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-01 07:59:04 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Judge(int n, int k, int m) {
static int i, j, kp, tk, tmp, lave;
static int pre, now, next[29];
for(i = 1; i < n; i++)
next[i] = i+1;
next[n] = 1, pre = n, now = 1, lave = n;
for(i = 1; i <= m; i++) {
tmp = 0;
tk = k%lave;
if(tk == 0) tk = lave;
for(j = now; tmp != tk-1; pre = j, j = next[j])
tmp++;
kp = j;
next[pre] = next[kp], now = next[kp], lave--;
if(kp <= m) return 0;
}
return 1;
}
main() {
int m, k, i, Ans[14];
for(i = 1; i <= 13; i++) {
k = i, m = k+1;
while(1) {
if(Judge(2*k, m, k))
break;
m++;
}
Ans[i] = m;
}
while(scanf("%d", &k) == 1 && k)
printf("%d\n", Ans[k]);
return 0;
}
內容 ：
有一個惡名昭彰的 故事：某部落酋長有n個俘虜（編號從1,2,3,……,n），他叫他們排成一個圈圈，然後開始數，第m 個人要被煮來吃掉（第一次從編號1的人開始數），按照此規則繼續下去，直到只剩下一個人，那一個人可以保留性命。例如：n=6, m=5則被吃掉的人的編號依序是5,4,6,2,3最號只有編號 1活了下來。Joseph 是個很聰明的人，他總是能挑到最後存留的位置，所以這件事才被披露出來。
現在假設共有2k個人，其中排在編號 1 到 k 的是好人，排在編號 k+1 到 2k 的是壞人，你的任務就是要找出一個最小的 m，使得在所有 k 個壞人被吃掉之前，沒有一個好人會被吃掉。
輸入說明
：
每行一個整數k（0<k<14）, k=0 代表輸入結束。
輸出說明
：
根據輸入的 k，輸出 m
範例輸入 ：
3 4 0
範例輸出 ：
5 30
提示
：
* Luck 貓翻譯
出處
：
ACM 305
作法 : 模擬+建表
/**********************************************************************************/
/* Problem: c108 "Joseph" from ACM 305 */
/* Language: C */
/* Result: AC (444ms, 228KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-01 07:59:04 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Judge(int n, int k, int m) {
static int i, j, kp, tk, tmp, lave;
static int pre, now, next[29];
for(i = 1; i < n; i++)
next[i] = i+1;
next[n] = 1, pre = n, now = 1, lave = n;
for(i = 1; i <= m; i++) {
tmp = 0;
tk = k%lave;
if(tk == 0) tk = lave;
for(j = now; tmp != tk-1; pre = j, j = next[j])
tmp++;
kp = j;
next[pre] = next[kp], now = next[kp], lave--;
if(kp <= m) return 0;
}
return 1;
}
main() {
int m, k, i, Ans[14];
for(i = 1; i <= 13; i++) {
k = i, m = k+1;
while(1) {
if(Judge(2*k, m, k))
break;
m++;
}
Ans[i] = m;
}
while(scanf("%d", &k) == 1 && k)
printf("%d\n", Ans[k]);
return 0;
}