8VC Venture Cup 2016 - Elimination Round |
---|
Закончено |
Назовём простой асимметрией набора чисел разность (не модуль разности) между средним значением и медианой. Вам дан список из n чисел, необязательно различных. Требуется выбрать какое-то непустое подмножество этих чисел (возможны повторения) с максимальным значением простой асимметрии.
Средним значением набора чисел является среднее арифметическое всех его элементов. Медианой набора чисел назовём средний элемент, если набор отсортирован. Для наборов чётного размера медианой будем называть среднее арифметическое двух средних элементов при сортировке.
В первой строке входных данных записано число n (1 ≤ n ≤ 200 000) — количество чисел в наборе.
Во второй строке записано n целых чисел xi (0 ≤ xi ≤ 1 000 000) — элементы набора.
В первой строке выведите число k (1 ≤ k ≤ n) — размер подмножества.
Во второй строке выведите k чисел — элементы выбранного подмножества в любом порядке.
Если оптимальных ответов несколько, то разрешается вывести любой.
4
1 2 3 12
3
1 2 12
4
1 1 2 2
3
1 1 2
2
1 2
2
1 2
В первом примере оптимальным подмножеством является со средним значением 5, медианой 2 и значением простой асимметрии 5 - 2 = 3.
Во втором примере оптимальным подмножеством является . Обратите внимание, что разрешены одинаковые элементы.
В последнем примере у любого подмножества среднее значение равно медиане, поэтому максимальная простая асимметрия равна 0.
Название |
---|