Mediana dinàmica P37064


Statement
 

pdf   zip

html

Donada una seqüència de paraules, escriviu la mediana de totes les paraules vistes a cada moment. Recordeu que la mediana d’un conjunt de n elements és aquell que es trobaria a la posició ⌊ (n + 1)/2 ⌋ si el conjunt estigués ordenat. Per exemple, la mediana de cinc elements és el tercer més petit, i la mediana de sis elements també és el tercer més petit.

Entrada

L’entrada consisteix en una seqüència de paraules minúscules diferents acabada en “END”.

Sortida

Per a cada paraula de l’entrada, escriviu la mediana de les paraules llegides fins al moment. Suposeu que les paraules s’ordenen en l’ordre alfabètic habitual.

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
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python