Description

Input

Output

链接

一、题意

        有k个好人和k个坏人，好人坐在前k个，后面坐着k个坏人。解约瑟夫环问题，要求好人全部存活。

二、思路

        数据量很小，直接暴力枚举可能的值，找到最小的。但是要注意必须打表，不然超时。

        对于约瑟夫环问题，假设编号为0开始，初始时cur指向0，每m个人淘汰一次，记out为出局人数。从cur开始，数m个数，到达编号为（cur+m-1）%（2*k-out）的人，该玩家被淘汰后，out++，并更新cur。这时使用一个技巧，就是将后面的所有人前移，补齐cur+m-1这个位置，则下一个淘汰的位置又是（cur+m-1）%（2*k-out）。所以只要在循环中判断每次被淘汰的人的编号是否小于k即可判断是否淘汰好人。

三、代码

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
const int MAXN = 100;
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
const int INF = 2000000000;//0x7fffffff
const double EPS = 1e-9;
const double PI = 3.14159265358979;
const int dir_4r[] = { -1, 1, 0, 0 };
const int dir_4c[] = { 0, 0, -1, 1 };
const int dir_8r[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dir_8c[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int ans[MAXN];

bool solve(int k, int m) {
	int out = 0;//出局人数
	int cur = 0;//当前位置
	while (out < k) {
		cur = (cur + m - 1) % (2 * k - out);//cur出局
		out++;
		if (cur < k)
			return false;
	}
	return true;
}

int main() {
	int k;
	memset(ans, 0, sizeof(ans));

	while (scanf("%d", &k) && k) {
		if (!ans[k])
			for (int i = k; ; ++i)
				if (solve(k, i)) {
					ans[k] = i;
					break;
				}
		printf("%d\n", ans[k]);
	}

	//system("pause");
	return 0;
}