| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11335 | Josephus Problem using doubly circular linked list |
|
| 11344 | Josephus Problem using 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.
Sample Input Download
Sample Output Download
Partial Judge Code
11335.cPartial Judge Header
11335.hTags
Discuss
Description
In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.
People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.
You're asked to solve this problem using circular linked list.
Input
The input has two positive integers, n (the number of people) and m (kill every mth people).
Output
The output is the order of people that were killed.