As operator of the communications centre, your job is to direct messages intercepted from the enemy to the decryption centre as to gather intelligence. Given the critical nature of the messages, your goal is to direct each encrypted message to the decryption centre with the shortest waiting time.
You will be given messages each containing alphanumeric characters. Assuming that it takes seconds to decrypt each message, output a list of the centres to direct the messages to in the order that they were given as to minimize the time it will take to decrypt all of them.
There are centres numbered from to . In the case of multiple suitable centres, choose the one with the smallest number.
The first line of input will contain , the number of messages.
The next lines of input will each contain a message of length .
The last line of input will contain , the number of centres at your disposal.
The output should consist of lines, each containing the centre every message will be directed to, in the order they were given.
3 We Love DMOPC 2
1 2 1
Explanation for Sample Output
Centres 1 and 2 both start off with a waiting time of zero, but 1 is chosen as it comes before 2. The waiting time for 1 is now 2 seconds. For the second message, centre 2 is chosen as its queue is empty. The third message is directed to centre 1 as it has a shorter waiting time ().
Note that all messages must be decrypted – the enemy might be trying to mislead the operator by encrypting it such that it appears as another message.
The order 1, 2, 1 will take 7 seconds, but 1, 1, 2 will only take 6 seconds, so why is 1, 2, 1 the correct answer?