Description

Input

Output

Sample Input

3
4
0

Sample Output

5
30

非常小的时候就有的约瑟夫问题，就是一群人(人数为n)围成一桌，从1到n标上号，然后来一个数m，每次数到m的人就被淘汰，从下一个人開始再数m个数，数到m的再被淘汰，就这么淘汰去吧。

这题是有n个好人，n个坏人。

好人的标号是从1到n，坏人的标号是从n+1到2*n。题目要找一个m，把坏人都淘汰掉，好人一个都不淘汰。

这题的关键在于不要纠结与坏人的标号，不论人数还剩多少，好人的标号始终是1到n。坏人的标号始终在后面。淘汰一个坏人。仅仅需把剩余的人数减1，剩下的坏人把之前淘汰的坏人填补上，穿好他们的标号就好。所以举个样例

6个人：1 2 3 4 5 6

m=5

第一次从1開始数5位，淘汰5，剩余 1 2 3 4 5(6就往前移一位。穿上5的衣服，这样好人就还是标号1 2 3，坏人标号4 5。剩余5个人)

第二次从5開始数5位，淘汰4。剩余 1 2 3 4 (好人标号1 2 3,坏人标号4)

第三次从4開始数5位，淘汰4。剩余1 2 3 。游戏结束。

为什么不要纠结于坏人的标号呢？由于不easy得出公式啊，如今不计较坏人的标号的话，我得到的公式就是

kill_num=(kill_num+m-1)%rest

所以我记录一个kill的vector，仅仅要每次淘汰的标号大于n或是等于0，即符合标准，我就把它扔进去，什么时候kill的人数等于n了。说明找到的m是正确的。否则就m++，再找。

(找m)代码：

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int people[50];
vector <int> kill;

int main()
{
	int n,k=0;
	while(cin>>n)
	{
		int result=n+1,rest=2*n,kill_num=1;
		int n2=2*n;
		
		memset(people,0,sizeof(people));
		kill.clear();
		while(1)
		{
			if(kill.size()==n)
				break;
			if((result+kill_num-1)%rest==0)
			{
				kill_num=rest;
				rest--;
				kill.push_back(rest);
			}
			else if((result+kill_num-1)%rest<=n)
			{
				kill_num=1;
				kill.clear();
				rest=n2;
				result++;
			}
			else
			{
				kill_num=(result+kill_num-1)%rest;
				rest--;
				kill.push_back(kill_num);
			}
		}
		cout<<result<<endl;
	}

	return 0;
}

#include <iostream>
using namespace std;

int main()
{
	int result[16];
	int n;
	
	result[1] = 2;
	result[2] = 7;
	result[3] = 5;
	result[4] = 30;
	result[5] = 169;
	result[6] = 441;
	result[7] = 1872;
	result[8] = 7632;
	result[9] = 1740;
	result[10] = 93313;
	result[11] = 459901;
	result[12] = 1358657;
	result[13] = 2504881;
	result[14] = 13482720;
	
	while(cin>>n && n)
	{
		cout<<result[n]<<endl;
	}
	return 0;
}