KidsGame | Topcoder Archive

Problem Statement

Little Johnny and his friends play a lot of games in which each player gets a different role. The roles are assigned using a method reminiscent of "eenie meenie miny moe" rhymes. n kids stand in a circle and are numbered from 1 to n going in a clockwise direction. They choose a number m, and starting with kid 1, they go around the circle in a clockwise direction, counting off from 1 to m. The kid who gets number m is eliminated from the circle, and the counting starts again at 1 with the next kid. The ith eliminated kid gets the ith role in the game. Johnny wants to know what role he will get if he is kid number k in the circle.

For example, consider the case where n = 5, m = 2, and k = 3. The kids are arranged clockwise as follows: 1, 2, 3, 4, 5. Starting with kid 1, they start counting from 1 to 2. Kid 2 gets number 2, so he is eliminated from the circle, which now looks like: 1, 3, 4, 5. They start counting again with kid 3. Kid 4 gets number 2 this time, so he is the next to get eliminated. Then, kid 1 is eliminated, followed by kid 5, and finally, kid 3. Johnny is kid 3, so he is the 5th kid to get eliminated, and he is assigned the 5th role.

Given n, m, and k, return the role assigned to Johnny. Roles are 1-indexed, so the 1st eliminated kid gets role 1, the 2nd eliminated kid gets role 2, and so on.

Definition

Class:: KidsGame
Method:: kthKid
Parameters:: int, int, int
Returns:: int
Method signature:: int kthKid(int n, int m, int k)
(be sure your method is public)

Constraints

n and m will be between 1 and 500000, inclusive.
k will be between 1 and n, inclusive.

Examples

```
5
```
```
2
```
```
3
```
```
Returns: 5
```
This is the example previously explained.
```
1
```
```
10
```
```
1
```
```
Returns: 1
```
There is only one kid, so he will be eliminated on the first step.
```
99
```
```
100
```
```
99
```
```
Returns: 94
```
```
19999
```
```
7
```
```
5
```
```
Returns: 18019
```
```
99999
```
```
11111
```
```
3
```
```
Returns: 69557
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.