POJ 1012 Joseph

Portal ：https://vjudge.net/problem/11573/origin

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

The question

   Yes k individual goodguy（ Number 1 ~ k）,k individual badguy（ Number k+1 ~ 2k）, Sit in a ring by number , Count in turn , To report for duty m The people of , Repeat the process . Solve the smallest m, Make all of badguy Than goodguy First of all .

Solving the algorithm

Here we assume that the number of rings is from 0 Start .
Observe the alarm m Continuity , about n Personally speaking , After Joseph Ring eliminated one person in the first round , The rest n-1 In fact, the individual has formed a new Joseph Ring , The difference is that the member numbers in the two Joseph rings are different . Therefore, we can understand that what needs to be solved here is a mapping relationship between different number sequences , It's going to be i+1 The number of the person eliminated by rotation is mapped to the i The corresponding number sequence in the wheel . First, the state transition equation is given ：

• $ans[0]=0（i==1）$
• $ans[i]=(ans[i-1]+m-1)/(n-i+1)（i>=1）$

Detailed derivation , You can push it yourself .
And then , We know m It must be k To 2k-1 Multiple （ from 0 Start numbering ）, So less traversal .
If you type a watch ：

jp[] = {
    0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720}

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 10010;
int jp[20];
int main(void)
{
    
    int n,m,k;
    while(~scanf("%d",&k)&&k){
    
        if(jp[k]){
    
            printf("%d\n",jp[k]);
            continue;
        }
        int ans[20]={
    0};
        n = 2*k;
        m = k;
        ans[0] = 0;
        for(int i=1;i<=k;i++){
    
            ans[i] = (ans[i-1]+m-1)%(n-i+1);
            if(ans[i]<k){
    
                if(m==n)    m = m+k;
                else   m++;
                i = 0;
            }
        }
        jp[k] = m;
        printf("%d\n",m);
    }
    return 0;
}