In the traditional game of Musical Chairs, N + 1
children run around N
chairs (placed in a circle) as long as music is playing. The moment the music stops, children run and try to sit on an available chair. The child still standing leaves the game, a chair is removed, and the game continues with N
children. The last child to sit is the winner.
In an attempt to create a similar game on these days' game consoles, you modify the game in the following manner: N
Children are seated on N
chairs arranged around a circle. The chairs are numbered from 1 to N
. Your program pre-selects a positive number D
. The program starts going in circles counting the children starting with the first chair. Once the count reaches D
, that child leaves the game, removing his/her chair. The program starts counting again, beginning with the next chair in the circle. The last child remaining in the circle is the winner.
<!-- MATH
$\epsfbox{p4368.eps}$
-->
WIDTH="624" HEIGHT="123" ALIGN="BOTTOM" BORDER="0"
SRC="/ntujudge/problemdata/704-1.png"
ALT="\epsfbox{p4368.eps}">
For example, consider the game illustrated in the figure above for N = 5
and D = 3
. In the figure, the dot indicates where counting starts and ×
indicates the child leaving. Starting off, child #3 leaves the game, and counting restarts with child #4. Child #1 is the second child to leave and counting restart with child #2 resulting in child #5 leaving. Child #2 is the last to leave, and child #4 is the winner. Write a program to determine the winning child given both N
and D
.