P2035 [USACO08JAN] iCow B

Exhausted by endless farm work, Farmer John plans to relax by listening to music on his newly purchased iCow in the MP3 player market. FJ’s iCow stores $N(1 \le N \le 1{,}000)$ songs, numbered $1..N$ in order. The playback order of the songs is determined by an algorithm designed by Farmer John: - The $i$-th song has an initial weight $R_i\ (1 \le R_i \le 10{,}000)$. - When a song finishes playing, the next song to play is the one with the maximum weight among all songs (if two or more songs have the same weight, the one with the smallest index among them is chosen). - After a song finishes playing, its weight is evenly distributed to the other $N-1$ songs, and its own weight becomes zero. - If a song’s weight cannot be evenly distributed (i.e., it is not divisible by $N-1$), then the remainder after division by $N-1$ will be distributed in units of $1$ to the songs earlier in index order (that is, song $1$, song $2$, and so on; of course, skip the song that just played), until the extra part is fully distributed. After the selected next song finishes playing, this algorithm is executed again to adjust the weights and select the following song. Please compute which songs are played first for the initial $T\ (1 \le T \le 1000)$ plays according to FJ’s algorithm.

The first line contains two integers separated by a space: $N$ and $T$. The second to the $(N+1)$-th lines: line $i+1$ contains one integer $R_i$.

Output $T$ lines. On the $i$-th line, output one integer, the index of the $i$-th song played by iCow.

Before each play, the weights of the three songs are: - $[10,8,11]$. Play $\#3$, $11/2 = 5$, remainder $1$. - $[16,13,0]$. Play $\#1$, $16/2 = 8$. - $[0,21,8]$. Play $\#2$, $21/2 = 10$, remainder $1$. - $[11,0,18]$. Play $\#3$... Translated by ChatGPT 5