首页 > 代码库 > UVa 130 - Roman Roulette

UVa 130 - Roman Roulette

题目:约瑟夫环变形,每次第k个出去后,他后面的第k个人站到他的位置,然后从这个位置继续;

            现在你的编号,是1号,问从几号开始你回剩到最后。

分析:数论,模拟。直接模拟计算即可。

            设从x位置开始则,最后剩下的人是s(编号0~n-1)有,你的新编号为m-x+1 = s,则x = m-s+1。

说明:看错题了,输出从1开始数的答案,WA了2次。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int p[101];

int find(int s, int k, int n)
{
	while (k) 
		if (p[s = (s+1)%n] != -1)
			k --;
	return s;
}

int main()
{
	int n,k,m;
	while (cin >> n >> k && n) {
		m = n;
		for (int i = 0 ; i < m ; ++ i)
			p[i] = i;
		int s = (k-1)%n;
		for (int i = 1 ; i < m ; ++ i) {
			p[s] = -1;
			swap(p[find(s, k, n)], p[s]);
			s = find(s, k, n);
		}
		printf("%d\n",(m-p[s])%m+1);
	}
    return 0;
}


UVa 130 - Roman Roulette