KidsGame
SRM 315 · 2006-08-09 · by Cosmin.ro
SRM 315 · 2006-08-09 · by Cosmin.ro · Recursion, Simple Search, Iteration
Problem Statement
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.
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.
Constraints
- n and m will be between 1 and 500000, inclusive.
- k will be between 1 and n, inclusive.
Examples
0)
10 3 6 Returns: 2
1)
10 3 4 Returns: 10
2)
1000 3000 7 Returns: 530
3)
500000 250000 93986 Returns: 358332
4)
5 2 3 Returns: 5
This is the example previously explained.
5)
1 10 1 Returns: 1
There is only one kid, so he will be eliminated on the first step.
Submissions are judged against all 125 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KidsGame with a public method int kthKid(int n, int m, int k) · 125 test cases · 2 s / 256 MB per case