| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10496 | problem1 |
|
Description
Josephus Problem with different steps
*** Problem Description ***
Base on the original Josephus Problem introduced in class, the rule of counting people is changed dynamically
according to a sequence of numbers.
For example, there are 10 people in a circle, and the sequence of countings is 3 4 5.
In the beginning, the step to kill m = 3. The sequence of killing people is as follows.
1, 2, 3 .....................(kill 3, and m is changed to 4)
4, 5, 6, 7 ..................(kill 7, and m is changed to 5)
8, 9, 10, 1, 2 ..............(kill 2, and m is changed to 3 again)
4, 5, 6 .....................(kill 6, and m is changed to 4)
8, 9, 10, 1 .................(kill 1, and m is changed to 5)
4, 5, 8, 9, 10 ..............(kill 10, and m is changed to 3 again)
4, 5, 8 .....................(kill 8, and m is changed to 4)
9, 4, 5, 9 ..................(kill 9, and m is changed to 5)
4, 5, 4, 5, 4 ...............(kill 4)
So the survivor is the 5th person.
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 first line of the input has two integers: n and k, where n is the number of total people,
and k is the number of countings. The number k is between 1 and 10.
The second line has k numbers, indicating the countings.
Output
Output is an integer: the number of the survivor. There is a newline at end.