Description
Base on the original Josephus Problem introduced in class, an additional rule of this problem is to change
direction of counting after killing a person. For example, there are 8 people, numbered 1 to 8, in a circle
and arranged in clockwise. The step to kill is 3.
The sequence of killing people is
1, 2, 3 (kill 3, change the direction to counter-clockwise)
2, 1, 8 (kill 8, change the direction to clockwise)
1, 2, 4 (kill 4, change the direction to counter-clockwise)
2, 1, 7 (kill 7, change the direction to clockwise)
1, 2, 5 (kill 5, change the direction to counter-clockwise)
2, 1, 6 (kill 6, change the direction to clockwise)
1, 2, 1 (kill 1)
So the person numbered 2 is the survivor.
Note there is a time limit to solve this problem: 3 seconds. If your algorithm or data structure
are not good enough, you will get 'Time Limit Exceeded' even though your program can solve the problem correctly.
Input
The input has two integers, n and m, where n is the number of total people, and m is the step to kill.
Output
The output is an integer: the survivor's number. There is a newline after that.
Tags