南郵 OJ 1597 約瑟夫問題

約瑟夫問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 253            測試通過 : 37 

比賽描述

17世紀的法國數學家加斯帕在《數目的遊戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須将一半的人投入海中，其餘的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就将他扔入大海，如此循環進行直到僅餘15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。這個故事的問題是經典的約瑟夫問題。

      現在我們知道有n個教徒和非教徒，其中非教徒數為m，将他（她）們按從1到n的次序放置到圓圈中，報數為k，要将所有非教徒投入大海，請按遞增次序給出非教徒在圓圈中的次序。

輸入

每行是用空格分開的三個整數，第一個是 n, 第二個是 m，第三個是k ( 0 <= m<n <=100，0 <k <=100)。最後一行是：

0 0 0

輸出

 對于每個測試用例，輸出一行，依次包含:

l         “Case #:”，#表示用例序号。

l         m個非教徒在圓圈中的次序，以空格分隔；如沒有非教徒，則無需輸出。

樣例輸入

6 2 9

12 4 8

8 3 2

0 0 0

樣例輸出

Case 1: 1 3

Case 2: 1 4 8 11

Case 3: 2 4 6

提示

題目來源

NUPT

/* Wrong Answer at Test 2
#include<iostream>
int main(){
	bool drop[101];
	int n,m,k,i,j,cas=0;
	while(scanf("%d%d%d",&n,&m,&k)==3 && n){
		cas++;
		printf("Case %d:",cas);
		if(!m){
			printf("\n");
			continue;
		}
		memset(drop,0,sizeof(drop));
		i = 0;
		while(m--){
			j = k;
			while(j){
				i = (i+1)%n;
				if(!drop[i]){
					j--;
				}
			}
			drop[i] = 1;
		}
		for(i=0;i<n;i++){
			if(drop[i]){
				printf(" %d",i);
			}
		}
		printf("\n");
	}
}
*/

#include<iostream>
int main(){
	bool drop[101];
	int n,m,k,i,j,cas=0;
	while(scanf("%d%d%d",&n,&m,&k)==3 && n){
		cas++;
		printf("Case %d:",cas);
		if(!m){
			printf("\n");
			continue;
		}
		memset(drop,0,sizeof(drop));
		i = -1;							//WA2
		while(m--){
			j = k;
			while(j){
				i = (i+1)%n;
				if(!drop[i]){
					j--;
				}
			}
			drop[i] = 1;
		}
		for(i=0;i<n;i++){
			if(drop[i]){
				printf(" %d",i+1);
			}
		}
		printf("\n");
	}
}