Description
Motivation
The new semester begins, and freshmen flood into ShanghaiTech. In order to welcome these new friends, a welcome game is held every year.[hw1.pdf]
Last year, a material tower model was left, waiting for a lucky buddy this year. New crazy game rules are designed for it. Only one person can derive this amazing model!
Game rule
-
“m” freshmen stand in a ring, and everyone is assigned an ID from 1 to “m” . (“m” is a positive integer) sequently. The game is round-based.
-
The first round begins at person with ID 1 in the circle. A counting proceeds around the circle following the ascending order(of ID), skipping n – 1 people, and removing the n_th player out of the game. (m <= n)
-
The i_th round begins after the person removed from the last round. A counting proceeds around the circle again following the ascending order(of ID), skipping n – i people, and removing the (n – i + 1 )_th player out of the game.(1 <= i <= m – 1).
-
The game ends after m – 1 round, left with a winner.
figure 1: the visualization of m = 5, n = 7
Goal
Your friend begs you to “hack” this game, since some position in this ring is sure to belong to the winner. You cannot wait to construct a script to figure out that position by C/C++.
Input
Two postive integer, “m”and “n”(1 <= m <= n), separated by a space.
For 50% cases, 1<=m<=n<=6000;
For 100% cases, 1<=m<=n<=100000, m*n<=10^9.
Output
A postive integer “p” (1 <= p <= m), denoting the ID of winner.
Details
Sample Input 1
100 200
Sample Input 2
2019 3000
Hint
Criterion
Sample Output 1
22
Sample Output 2
104
-
Review the C/C++ programming. After you manipulate the usage of the built-in array, you will reach the limited level (50 % of points).
-
After you manipulate the usage of the linked list, you will get the rest of points (100 % of points).
-
More fancy algorithms are welcome, but we strongly recommand you to practise the usage of the linked list.
