DMOPC '14 Contest 5 P2 - Redirection

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Input

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.


  • 0
    will31415  commented on July 3, 2017, 3:41 p.m.

    Why are some test cases working while others aren't????

  • 0
    kobortor  commented on Feb. 10, 2015, 5:24 p.m.

    On the 4th test case my program crashes before I even get to print anything at the very start.

    Is this an error with the judge or did you guys disable debugging RTEs.

    • 4
      FatalEagle  commented on Feb. 10, 2015, 5:27 p.m.

      Your output isn't flushed.