Description

(30 points)

There are n friends playing a game. They sit in a circle and are numbered from 1 to n in clockwise order.

You are also given an integer k. The game starts from friend 1, and proceeds according to the following rules:

• Moving clockwise from the i-th friend brings you to friend (i + 1) for all 1 ≤ i < n, and moving clockwise from friend n brings you back to friend 1.

Game Rules

1. Start at friend 1.

2. Count k friends in the clockwise direction, including the current friend as the first count.
   The counting wraps around the circle as necessary.

3. The friend who is counted as the k-th leaves the circle and is eliminated from the game.

4. If more than one friend remains, the next round starts from the friend immediately clockwise of the one who was just eliminated, and the process repeats.

5. When only one friend remains, that friend is declared the winner.

Task

Given the integers n and k, return the label of the friend who wins the game.

For Example,

Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

 

For more Information about this problem, you can read it after the exam.

Note that the problem is named after Flavius Josephus, a Jewish historian and leader who lived in the 1st century. According to Josephus's firsthand account of the siege of Yodfat, he and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves. (The above descriptions are from wikipedia and it is the case that n = 41 and k = 5, where the last two survivors are numbered 16 and 31, you can take this as the input/output case. )

Input

• An integer n — the number of people in the circle.

• An integer k — the counting step.

• Constraints:
  1 ≤ k ≤ n ≤ 500

Output

Return the label (1 to n) of the only person left in the circle, who becomes the winner of the game.

Sample Input  Download

Sample Output  Download

Tags

Discuss