POJ 1012 -- Joseph

POJ 1012 -- Joseph

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30

k个好人与k个坏蛋站一圈，前k个都是好人，从1开始报数，报道m的枪毙，下一个再从1开始报数，以此类推！求一个数m，当剩下k个人时，满足他们都是好人

a[j]为第j次退出圈的人的编号（从0开始），每退出一个人，圈就缩小，圈中的人的

编号就相应的改变，这点很重要！！！比如k=5时，3个退出的人的编号

 依次是4、3、3，对应开始时的编号就是5、4、6

设a[i]表示第i个出局者的位置，a[i-1]表示第i-1个出局者的位置，则

a[i]=a([i-1]-1+m)%len (len表示当前人数)

剪枝为：前k个人的编号永远不变，若退出的人在前k个人之前，则该方案错误

                即if(a[j]<k) break;

http://chaoshuimm.iteye.com/blog/1039305

1. /*  
2. 　测试ｍ是否满足要求 
3. 　k: 有2ｋ个人 
4. 　ｍ：每数到ｍ就出局 */  
5. bool test(int k, int m) {  
6.     int i = 0, len = 2 * k;　//len: 当前总人数  
7.     while(len > k) {  
8.         i = (i + m - 1) % len;  //每次出局人是出局前的len 个人中的第i 个, 下标从0 开始  
9.         if(i < k)      
10.             return false;  
11.         len--;  //没出局一个,修改len  
12.     }  
13.     return true;  
14. }  
15.   
16. int main() {  
17.     int k;  
18.     int a[14] = {0};    //数组保存计算过的数据, 不保存的话会超时,  
19.                         //其实很无聊,就14个数据,还整这么大的数据量  
20.     while(scanf("%d", &k) && k) {  
21.          if(!a[k]) {    //如果a[k]为0 就进行测试  
22.             int t = k + 1;  //测试从k+1开始,下于K+1的测试没必要  
23.             while(true) {  
24.                 if(test(k, t)) {  
25.                     a[k] = t;  
26.                     break;  
27.                 }  
28.                 else  
29.                     t++;  
30.                 if(t == 2 * k)//跳过不必要的测试  
31.                     t += k + 1;  
32.             }  
33.         }  
34.         printf("%d\n", a[k]);  
35.     }  
36.     return 0;  
37. } 

  据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

  本题类似于这样一则描述：17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

http://fayaa.com/code/view/26765/
http://www.cnblogs.com/pcwl/archive/2011/04/26/2029188.html
http://www.xuebuyuan.com/723343.html
Read full article from 1012 -- Joseph