IMPC - 2013-2014 |
Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 9000/7000/7000/7000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Hot Potato
The Josephus problem is the following game: n people, numbered 1 to n, are sitting in a circle.
Starting at person 1, a hot potato is passed. After m passes, the person holding the hot potato
is eliminated, the circle closes ranks, and the game continues with the person who was sitting
after the eliminated person picking up the hot potato. The last remaining person wins. Thus, if m = 0
and n = 5, players are eliminated in order, and player 5 wins. If m = 1 and n = 5, the order of
elimination is 2, 4, 1, 5.
| First sitting plan: | 1 2 3 4 5 | 1 is the active | |
| 1st pass | 1 3 4 5 | 2 is eliminated, | 3 is the active one |
| 2nd pass | 1 3 5 | 4 is eliminated, | 5 is the active one |
| 3rd pass | 3 5 | 1 is eliminated, | 3 is the active one |
| 4th pass | 3 | 5 is eliminated, | 3 is the winner |
Input specification
You are given two integer numbers: the number of people in the circle (n) and the number of passes (m) before every remove
where 1 ≤ n ≤ 10000 and 0 ≤ m ≤ 2000
Output specification
Show one integer winning the game.
Sample Input I:
5 3
Sample Output I:
1
Sample Input I:
10 2
Sample Output I:
4
Для отправки решений необходимо выполнить вход.
|