iCow
Time limit1sMemory limit128 MB
Repeatedly pick the highest-rated song, reset its rating to 0, and spread its points over the others until T songs are played.
- Level
Medium4 of 10
- Topics
- Simulation, Implementation, Greedy
- Solved
- No attempts yet
Problem
Weary from the endless toil of farming, Farmer John has decided to try the MP3 player market with his new iCow. The iCow stores songs (), numbered through , and plays them in a "shuffled" order determined by Farmer John's own algorithm:
- Each song has an initial rating ().
- The next song to be played is always the one with the highest rating. If two or more songs are tied, the one with the smallest index is chosen.
- Once a song is played, its rating is set to , and the points it held are distributed evenly among the other songs.
- If the points cannot be distributed evenly (that is, they are not divisible by ), the leftover points are handed out one at a time to the lowest-numbered songs first (, , and so on, but never the song that was just played) until no leftover points remain.
- After the next song is played, this process repeats with the updated ratings.
Determine the first songs () that the iCow plays.
Input
- Line 1: Two space-separated integers, and .
- Lines 2 to : Line contains a single integer .
Output
- Lines 1 to : Line contains the index of the -th song that the iCow plays.