And Then There was One Turkey Left
(2011-ish)
Description
The U. of T. Engineering “Skule”
— boo, hiss! —
has a tradition at their big Thanksgiving bash.
At the end of their potluck feast,
they play a game
—
And Then There was One Turkey Left
—
to decide who
gets to take all the leftovers home.
This person gets named the last turkey.
(Leftovers of dishes prepared by U. of T. engineering students?!
Blech!)
The attendees of the U. of T. Engineering “Skule”
— boo, hiss! —
Thanksgiving bash
all sit around on giant table.
Consider them numbered 1,..., n clockwise.
Two numbers are provided: k and m.
From this,
people are made to leave the table one by one by the following rules,
until only one remains
(the one turkey left).
- Make person m leave.
- Locate the k-th person clockwise from m and
make him or her leave.
- In subsequent steps,
start from the seat of the person removed in the last step,
make k hops clockwise over the remaining people,
and make the one you reach leave.
In other words,
skip (k - 1) remaining people clockwise,
and remove the next one.
Repeat this until only one person is left,
and answer his or her number.
For example,
the answer for the case n = 8 , k = 5 , m = 3 is 1, as shown.
- Initial State
Eight people are arranged in a circle,
around the table.
- Step 1
Person 3 is removed since m = 3 .
- Step 2
You start from the seat that was occupied by person 3.
You skip four people 4, 5, 6 and 7 (since k = 5 ),
and remove the next one, which is 8.
- Step 3
You skip people 1, 2, 4 and 5, and thus remove 6.
Note that you only count people that are still at the table
(in the circle),
ignoring those seats from which people have already been removed.
(So person 3 is ignored,
in this case.)
- Steps 4–7
You continue until only one person is left.
Notice that in later steps when only a few people remain,
the same person may be skipped multiple times!
For example, people 1 and 4 are skipped twice in step 7.
- Final Step
Finally, only one person, 1, is still at the table
(in the circle).
This is the final step,
so the answer is 1.
Input
The input consists of multiple datasets each of which is formatted as
follows.
n k m
The last dataset is followed by a line containing three zeros.
Numbers in a line are separated by a single space.
A dataset satisfies the following conditions:
- 2 ≤ n ≤ 10,000
- 1 ≤ k ≤ 10,000
- 1 ≤ m ≤ n
The number of datasets is less than 100.
Output
For each dataset,
output a line containing the number of the person left
—
the one turkey left!
—
in the final state.
No extra characters such as spaces should appear in the output.
Sample Input
8 5 3
100 9999 98
10000 10000 10000
0 0 0
Sample Output
1
93
2019