POJ 1012 Joseph

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

Source

Central Europe 1995

題意：同樣的約瑟夫問題，只是現在有K個好人，K個壞人，確定一個步長，是的在第一個好人被清除之前所有壞人都被清除干凈。

題解：

1.壞人被清除掉的先后順序無關緊要，知道下一個除掉的是好人還是壞人就行了。
2.由于好人一直都是k個，每除掉一個壞人，壞人數-1，所以隊列的總數每次-1但是好人一直是前k個
3.下一個被清除的人在隊列中的“相對”序號為 s = (s+m-1)%(n-i);
4.只要s>=k，那么下一個被除掉的就是壞人

5.接下來說說m的取值范圍：我們考察一下只剩下k+1個人時候情況，即壞人還有一個未被處決，那么在這一輪中結束位置必定在最后一個壞人，那么開始位置在哪呢？這就需要找K+2個人的結束位置，然而K+2個人的結束位置必定是第K+2個人或者第K+1個人，這樣就出現兩種順序情況：GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2個人的那一輪退出的人）所以有K+1個人的那一輪的開始位置有兩種可能即第一個位置或K+1的那個位置，限定m有兩種可能：t(k+1) 或 t(k+1)+1; t>=1; 若遍歷每一個m必定超時，避免超時則需要打表和限制m的范圍。

下面給出AC代碼：

 1 #include <cstdio> 2 //#include <bits/stdc++.h> 3 using namespace std; 4 int a[14]; 5 int f(int k,int m) 6 { 7     int n,i,s; 8     n=2*k; 9     s=0;10     for(i=0;i<k;i++)11     {12         s=(s+m-1)%(n-i);13         if(s<k) return 0;14     }15     return 1;16 }17 int main()18 {19     int i,k,n;20     for(k=1;k<=14;k++)21     {22         i=k+1;23         while(1)24         {25             if(f(k,i))26             {27                 a[k]=i;28                 break;29             }30             else if(f(k,i+1))31             {32                 a[k]=i+1;33                 break;34             }35             i+=k+1;36         }37     }38     while(scanf("%d",&n)&&n)39     printf("%d\n",a[n]);40     return 0;41 }