Medians


Submit solution


Points:100 (partial)
Time limit:0.35s
Memory limit:32M
Author:

Tags
Trees
Difficulty
Easy

Write a program that supports three operations:

  • ADD number
    • Adds a number to a sequence
  • FIND
    • Finds the median of the sequence
  • EXIT
    • Stops the program

Median is defined as follows:

  • If the count of numbers in the sequence is odd:
    • The median is the middle number by value, not average
    • Example: the sequence 5 1 2 3 1 has median 2
  • If the count of numbers in the sequence is even:
    • The median is the average between the two middle values:
    • Example: the sequence 5 1 2 3 1 3 has median 2.5

Input

  • Read from the standard input

  • On each of the input, you will find one of the three commands

    • 'ADD number' - perform ADD command
    • 'FIND' - perform 'FIND' command and print the median
    • 'EXIT' - stop reading commands

Output

  • Print to the standart output

  • Print the median for each FIND command

Constraints

  • The commands are always less than 131074
  • Each number is always between -2^15 and 2^15

Sample tests

Input

ADD 5
ADD 1
ADD 2
FIND
ADD 3
FIND
ADD 1
FIND
EXIT

Output

2
2.5
2

Input

ADD 5
ADD 1
FIND
ADD 2
FIND
ADD 3
ADD 1
FIND
ADD 3
FIND
EXIT

Output

3
2
2
2.5

Comments


  • 0
    stanil_dimitrov
     commented on Nov. 27, 2018

    Благодаря, колега... Така ми мина, задачата(без последните 2 теста, за time limit). Все пак как се разбира, това за сортирането, при условие, че не е написано никъде в условието?


    • 0
      stanislav.p.dinev
       commented on Nov. 28, 2018

      Всъщност има такова понятие медиана на напоредица от числа и алгоритъма за търсене е след предварително ранжиране на поредицата (сортиране).


    • 0
      petar_nenov
       commented on Nov. 27, 2018

      Досетих се от примерите и от това, че някой е успял.;)


      • 0
        stanil_dimitrov
         commented on Nov. 27, 2018

        Ок, благодаря :)


  • 0
    petar_nenov
     commented on Nov. 27, 2018

    Привет, Поредицата трябва да бъде сортирана преди FIND в нарастващ ред ;)


  • 0
    stanil_dimitrov
     commented on Nov. 27, 2018 edit 2

    Колеги някой може ли да обясни идеята на тая задача, защото като ги смятам ръчно подадените данни, не съвпадат с дадения output... Примерно при първия пример, се подават първо цифрите 5, 1, 2 и след това се подава команда за търсене...и спрямо условието се иска средния елемент, при поредица с нечетна дължина, демек 1 -та, а в output дават 2 -ка ? Как се получава тази двойка? Това важи и за следващия пример, първо се подава 5 и 1, със средноаритметично 3, след това се подава 2 и поредицата става съответно 5, 1, 3 и пак резултат e 2?


    • 0
      ivan.kirov
       commented on Nov. 28, 2018

      Ако са нечетен брой (2k + 1), медианата e k+1-вата стойност от стойностите в сортиран ред. Ако са четен брой (2k) e средно-аритметично от k и k+1-вата стойност.

      A, B, C, D, E => медианата е C.

      A, B, C, D => медианата е (B+C)/2