Mediana dinàmica P37064


Statement
 

pdf   zip

thehtml

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 C++ Python