|Online MIPT programming contest||РУССКИЙ|
Time limit = 3 second(s)New company "Audio square" have conqured the major part of online audio streaming market. It provides personal radio for each human. But now "Audio Square" CEOs decided to publish new feature Public Radio.
Public Radio has one audio stream where tracks successively change each other.
Its algorithm is simple but still promises considerable social satisfaction. Visitors of the public radio web site vote for tracks they want to listen or don't want to listen thus changing track_score of the tracks. One IP address is allowed to vote only once in 10 minutes (two votes should be separated by 600 seconds or more).
Next track is the track with maximum score. If two tracks have equal score track with lower id is preferred one. The moment track starts to play its score resets to -1.
You are the chief developer of "Audio square". You have professional stuff to do the job, but this time you prefer to do it by yourself (to revive your professional programmer skills).
Your task is to make algorithm efficient so that radio does not use much processor time and memory.
The program interacts with server via standard input/output and uses the following protocol.
Each input line is command. There are three command types:
The command VOTE change track_score of the given track with id track_id. Its arguments are
Response to VOTE is new track_score (even if it have not changeed)
The command GET is used to get next track to play. The response is pair track_id and track_score separated by space. Just after this command track_score of the track should be reset to -1.
The command EXIT is in the last line. The response is line ``OK''.
Number of commands is less than 100002.
The initial value of track_score is equal to 0 for all tracks.
Commands in input are odered by execution time.
Output should contain the same number of lines as input. Each line contains response to corresponding command from input.
GET VOTE 188.8.131.52 1 -1 1 VOTE 184.108.40.206 2 1 2 VOTE 220.127.116.11 1 2 4 VOTE 18.104.22.168 1 4 20045 GET GET GET VOTE 22.214.171.124 3 -1 20049 EXIT
1 0 -2 0 -2 2 1 2 2 0 3 0 -2 OK
GET GET GET VOTE 192.168.0.1 2 2 11111111 EXIT
1 0 2 0 3 0 1 OK
Artem Voroztsov, Personal Programming MIPT Contest, 7 October 2007.
4 December 2007
© acm.mipt DevGroup
The page was generated in 190ms