HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data structures: Stacks, Queues, Linked Lists, etc > problem:


50774 - Hot Potato

Guest
• Review clarifications (1)

Section problems

• 50262 - Brackets
• 50291 - Postfix Arithmetic Expressions
• 50286 - Remove Duplicates
• 50775 - Balanced Parenthesis
• 50340 - Game 19
• 50877 - Friendly Queue
• 51086 - Top popular student
• 50774 - Hot Potato
• 50777 - Dwarfs Maze
• 50781 - ReversesreveR
• 50780 - Hot Potato - Revisited
• 50564 - Mother's Milk Buckets
• 50636 - Brackets
• 50776 - The number of different pa...
• 50779 - The shortest path in a maze

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 pass1 3 4 5  2 is eliminated,  3 is the active one
  2nd pass1 3 5   4 is eliminated, 5 is the active one
  3rd pass3 5   1 is eliminated, 3 is the active one
  4th pass3   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


Для отправки решений необходимо выполнить вход.

www.contester.ru