Dynamic median P37064


Statement
 

pdf   zip

html

Given a sequence of words, print the median of all the words seen so far at every moment. Please recall that the median of a set of n elements is the element that would be in the position ⌊ (n + 1)/ 2 ⌋ if the set was ordered. For example, the median of five elements is the third smallest, and the median of six elements is also the third smallest.

Input

Input consists of a sequence of different lowercase words ended in “END”.

Output

For every word in the input, print the median of the words read so far. Suppose that the words are sorted with the usual alphabetical order.

Public test cases
  • Input

    hola
    bye
    adeu
    hi
    hello
    END
    

    Output

    hola
    bye
    bye
    bye
    hello
    
  • Input

    a
    b
    c
    d
    e
    f
    END
    

    Output

    a
    a
    b
    b
    c
    c
    
  • Input

    f
    e
    d
    c
    b
    a
    END
    

    Output

    f
    e
    e
    d
    d
    c
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python