Roman Roulette(约瑟夫环模拟)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Roman Roulette

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 286 Accepted Submission(s): 105

Problem Description

The historian Flavius Josephus relates how, in the Romano-Jewish conflict of 67 A.D., the Romans took the town of Jotapata which he was commanding. Escaping, Jospehus found himself trapped in a cave with 40 companions. The Romans discovered his whereabouts and invited him to surrender, but his companions refused to allow him to do so. He therefore suggested that they kill each other, one by one, the order to be decided by lot. Tradition has it that the means for effecting the lot was to stand in a circle, and, beginning at some point, count round, every third person being killed in turn. The sole survivor of this process was Josephus, who then surrendered to the Romans. Which begs the question: had Josephus previously practised quietly with 41 stones in a dark corner, or had he calculated mathematically that he should adopt the 31st position in order to survive?

Having read an account of this gruesome event you become obsessed with the fear that you will find yourself in a similar situation at some time in the future. In order to prepare yourself for such an eventuality you decide to write a program to run on your hand-held PC which will determine the position that the counting process should start in order to ensure that you will be the sole survivor.

In particular, your program should be able to handle the following variation of the processes described by Josephus. n > 0 people are initially arranged in a circle, facing inwards, and numbered from 1 to n. The numbering from 1 to n proceeds consecutively in a clockwise direction. Your allocated number is 1. Starting with person number i, counting starts in a clockwise direction, until we get to person number k (k > 0), who is promptly killed. We then proceed to count a further k people in a clockwise direction, starting with the person immediately to the left of the victim. The person number k so selected has the job of burying the victim, and then returning to the position in the circle that the victim had previously occupied. Counting then proceeeds from the person to his immediate left, with the kth person being killed, and so on, until only one person remains.

For example, when n = 5, and k = 2, and i = 1, the order of execution is 2, 5, 3, and 1. The survivor is 4.

Input

Your program must read input lines containing values for n and k (in that order), and for each input line output the number of the person with which the counting should begin in order to ensure that you are the sole survivor. For example, in the above case the safe starting position is 3. Input will be terminated by a line containing values of 0 for n and k.

Your program may assume a maximum of 100 people taking part in this event.

Sample Input

1 1
1 5
0 0

Sample Output

1 1

题解：

历史学家弗拉维·约瑟夫曾讲述过这样的故事：在公元前67年的罗马犹太战争中，罗马攻下了他掌权的城市。随后，他与另外40个反抗战士一起逃到了一个山洞中而被困在里面。罗马人发现了他的下落并劝他投降，但他的战士们拒绝投降。于是他提议互相杀死对方，一个接一个，顺序由大家决定。有一种传统的方式，即为了公平起见所有人都站成一个环，从某一点开始，循环计数，每隔两个活着的人就杀掉一个。最后只有约瑟夫幸存了下来，投降了罗马。问题来了，约瑟夫如何知道一开始站第31位才会幸存到最后呢？是不是趁着洞穴黑暗大家没注意，悄悄地用41个石子演练过了？还是他用数学方法计算出了这个位置？

在仔细读过这个故事由来后，你逐渐克服了恐惧心理，不再害怕将来这种事会发生到你的头上。但为了应对这种类似的情况，你准备为你的手机写一个程序，以便快速的计算这个过程并确保你能站到最后幸存的位置上。

类似于约瑟夫所述的问题，你的程序需要处理如下改编过的问题。最初n（n > 0）个人面朝内围成一个环，并依次按顺时针编号1到n。你的编号为1，第一个轮到的人编号为i，同样顺时针方向开始计数，直到第k（k > 0）个人把他杀掉。然后再从下一个还活着的人开始向后数到第k个人，由这个人来把刚才杀掉的人埋葬，并站到被杀的人的位置上。然后再从他左面第一个还活着的人开始计数，杀掉第k个人，以此类推，直到只有一个人还活着。

比方说，n = 5，k = 2，i = 1，被杀的顺序应为：2、5、3和1。4幸存。

分析

类似于经典的约瑟夫环问题，这类问题都是可以用数学推导求出通式的。但这道题目的过程要远比约瑟夫环问题复杂得多，分析通式比较困难，且由于数据量很小（少于100人），可直接按模拟类型的题目对待求解。

模拟的实现使用动态数组是非常方便的，过程也很简单。数组初始存储每一个人的编号，从第0个元素（1号）开始计数，每次杀死一个人前先不要将这个人的编号删除，而是先找出要来埋他的人，将他们的编号互换，然后将埋他的人原来所在的位置删掉即可。最后计算出的是从1号开始计数，最后能幸存的人编号p，那么从你前面第p个人开始你就是安全的（你站在第1位），即n – p。这个换算的原理是显而易见的。

这个是找你前面第p个人开始你就是安全的；

由这个人来把刚才杀掉的人埋葬，并站到被杀的人的位置上

题解：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define mem(x,y) memset(x,y,sizeof(x))
/*#define L tree[root].l
#define R tree[root].r
#define S tree[root].sum
#define NOW tree[root<<1].sum+tree[root<<1|1].sum
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r*/
using namespace std;
const int INF=0x3f3f3f3f;
vector<int>vec;
int main(){
int n,k,flot=;
while(scanf("%d%d",&n,&k),n|k){
vec.clear();
for(int i=;i<=n;i++)
vec.push_back(i);
int pos=,kisp=(k-)%vec.size();
while(vec.size()>){
pos=(kisp-+k)%(vec.size()-);
pos=(pos+(pos>=kisp))%vec.size();
vec[kisp]=vec[pos];
vec.erase(vec.begin()+pos);
kisp=(kisp+k-(pos<kisp))%vec.size();
}
printf("%d\n",(n - vec.front() + ) % n + );
//printf("Case %d: %d\n",++flot,*vec.begin());
}
return ;
}