POJ 1012：Joseph

 

Joseph Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 50068   Accepted: 19020

 

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

很小的時候就有的約瑟夫問題，就是一群人(人數為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 ，游戲結束。

為什麼不要糾結於壞人的標號呢？因為不容易得出公式啊，現在不計較壞人的標號的話，我得到的公式就是

kill_num=(kill_num+m-1)%rest

所以我記錄一個kill的vector，只要每次淘汰的標號大於n或是等於0，即符合標准，我就把它扔進去，什麼時候kill的人數等於n了，說明找到的m是正確的，否則就m++，再找。

(找m)代碼：

 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int people[50];
vector  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<
 
 
最終打表代碼：
 
#include 
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<