Medians - Easy
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Най-накрая дойде момента за нанасяне на оценките по ДАА. Ели и колегите ѝ стоят в очакване да дойде и техния ред за това. Като при повечето изпити, след излизането на всеки от студентите, той веднага бива наобиколен от няколко свои колеги да бъде обстойно разпитан какво са го питали и колко са му писали. По досегашните оценки студентите, които все още не са минали, могат да определят каква е средната оценка.

Елеонора е забелязала, че медианата на досегашните оценки е далеч по-добра метрика колко "гаден" е даден изпит, отколкото средно аритметично. Медиана на N числа е числото, което получаваме като сортираме N-те числа и:
  • Вземем това по средата, ако N е нечетно
  • Вземем средното аритметично на двете числа по средата, ако N е четно

Ели няма никакъв проблем да намира медианата наум, независимо колко много студенти има на изпита. Вие, за съжаление, нямате нейните възможности и затова решавате да си напишете програма, която прави това. По даден брой N на студентите, които минават преди вас, вие искате да намерите медианата на досега миналите след излизането на всеки от тях (тоест първо медианата на първия, после медианата на първия и втория, после медианата на първия, втория и третия и т.н.).
Вход
Стандартният вход съдържа два реда, като на първия от тях е зададен броят на студентите N. На втория ред ще има N цели числа A1, A2, …, AN, разделени с по един интервал – оценките на всеки от студентите. Университетът, в който учи тя (СУортс), е малко странен и оценките са между 1 и 30,000, включително.
Изход
На единствен ред на стандартния изход изведете N числа, разделени с по един интервал – i-тото от които е медианата на първите i числа. Изведете числата с точно една цифра след десетичната точка.
Ограничения
  • 1 ≤ N ≤ 10,000
  • 1 ≤ Ai ≤ 30,000
Примерен Вход Примерен Изход
5 42 13 11 17 666 42.0 27.5 13.0 15.0 17.0
7 1 2 3 4 5 6 7 1.0 1.5 2.0 2.5 3.0 3.5 4.0
След като решите тази задача, можете да пробвате Medians (Hard) - по-трудна нейна версия.
Мрън!