约瑟夫环
时间限制:1s 内存限制:128M
题目描述
约瑟夫环的问题已经总所周知了,有
$n$个人围成一个环,编号为 $1,2,…,n$,从第一个人开始报数,报到$m$的人退出这个环。退出的一个人从$1$开始继续报数,知道只剩下一个人。比如$n=3,m=2$,首先$2$出列,然后$1$出列,只剩下$3$。
现在的问题是有$k$个好人和$k$个坏人,按照顺序站成一个圈,前$k$个是好人,后$k$个是坏人。你需要确定一个最小的$m$,使得第$1$到第$k$个出列的人都是坏人,即当约瑟夫环只剩下$k$个人时,剩下的都是好人(编号从$1$到$k$)。
输入格式
包含多组测试数据,需要注意,测试数据最多的时候可以有$10000$组。
每组测试数据包含一个整数$k(1≤k≤13)$
当读入$0$时,测试结束
输出格式
对于每个测试数据,输出一行,包含一个整数,表示最小的$m$
解题思路
这个题虽然是约瑟夫,但是不需要去模拟,只需要去取模判断即可。
每次询问后把答案记录下来,下一次直接用,就可以大大提升效率 ( 重要!)
C++ Code
#include <cstdio>
using namespace std;
int k,m = 1,beginn = 1;
int ans[105];
bool check(int mod) {
int t = (beginn + m - 1) % mod;
if (t >= k) {
beginn = t;
return true;
}
return false;
}
int main() {
while(1) {
scanf("%d", &k);
if (ans[k] != 0) {
printf("%d\n", ans[k]);
continue;
}
if (k == 0) break;
m = k;
bool flag = false, flag2 = false;
while (1) {
beginn = 0;
flag2 = 0;
for (int i = 0; i < k; i++) {
if (!check(2 * k - i)) {
flag2 = 1;
break;
}
}
if (!flag2) break;
m++;
}
ans[k] = m;
printf("%d\n",m);
}
return 0;
}