DMOPC '14 Contest 4 P2 - Redirection

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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 N messages each containing C alphanumeric characters. Assuming that it takes C 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 M centres numbered from 1 to M. In the case of multiple suitable centres, choose the one with the smallest number.

Input Specification

The first line of input will contain N (1 \le N \le 100), the number of messages.

The next N lines of input will each contain a message of length C (1 \le C \le 100).

The last line of input will contain M (1 \le M \le 20), the number of centres at your disposal.

Output Specification

The output should consist of N lines, each containing the centre every message will be directed to, in the order they were given.

Sample Input


Sample Output


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 (2 < 4).

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.


  • 2
    LeoLi1119  commented on May 4, 2022, 4:45 p.m.

    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?