Choir circle cuts
HardOnline Assessment
Find who is left standing when a choir director thins out a circle of singers with a deck of counting cards.
singers singers stand in a circle on the risers, numbered 1 to singers clockwise. The director keeps a deck of step cards cards, used over and over in order (cards[0], cards[1], ..., then cards[0] again after the last).
The thinning goes in rounds until one singer is left:
- The starter of the first round is singer 1.
- In a round the director turns the next card, with value
s, and countsssingers clockwise, beginning with the starter as count 1. The singer reached by countsis cut and leaves the circle. (Ifsis larger than the number of singers left, the count simply keeps going around.) - The next round's starter is the singer immediately clockwise of the one just cut.
The singer who is never cut is the winner. The runner-up is the singer cut in the very last round (when two singers were left). If only one singer was there to begin with, there is no runner-up.
For example, with 5 singers and cards [2, 3]: round 1 counts 1, 2 and cuts singer 2; round 2 starts at singer 3 and counts 3, 4, 5, cutting singer 5; and so on.
Input: singers, an integer, and cards, a list of integers.
Output: [winner, runner_up], both singer numbers; the runner-up is 0 when singers is 1.
Example 1
- Input:
- [5,[2,3]]
- Output:
- [1,4]
- Explanation
- Singers 1-5 with cards 2, 3, 2, 3. Round 1 (card 2) starts at 1: counts 1, 2, cuts 2. Round 2 (card 3) starts at 3: counts 3, 4, 5, cuts 5. Round 3 (card 2) starts at 1 (clockwise of 5): counts 1, 3, cuts 3. Round 4 (card 3) starts at 4 with singers 1 and 4 left: counts 4, 1, 4, cuts 4. Singer 1 wins and the last cut was singer 4:
[1, 4].
Example 2
- Input:
- [2,[5]]
- Output:
- [2,1]
- Explanation
- With two singers and a card of 5 the count goes 1, 2, 1, 2, 1 and lands on singer 1, who is cut. Singer 2 wins and the runner-up is singer 1:
[2, 1].
Example 3
- Input:
- [9,[1,4,2]]
- Output:
- [3,6]
- Explanation
- With 9 singers the deck reads 1, 4, 2, 1, 4, 2, 1, 4. The cuts are 1, 5, 7, 8, 4, 9, 2 and finally 6 (the count from singer 3 goes 3, 6, 3, 6), so singer 3 wins and singer 6 is the runner-up:
[3, 6].
Constraints
1 <= singers <= 10^121 <= len(cards) <= 81 <= cards[i] <= 20