| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11335 | Josephus Problem using doubly circular linked list |
|
Description
Based 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.
You're asked to solve this problem using circular linked list.
You will be provided with main.c and function.h, and you need to implement function.c.
Note there is a time limit to solve this problem: 3 seconds.
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.