Задача №112544. Игра на бирже
Петя пишет программы для бирж. Он занимается разработкой различных финансовых инструментов, его последний проект связан с анализом возможности арбитража с использованием исторических данных о котировках существенно волатильной акции.
Идея анализа состоит в следующем: по заданным котировкам акции в течение n последовательных дней, требуется выбрать подпоследовательность котировок, которая удовлетворяет следующему свойству: любые две соседние котировки в выбранной подпоследовательности должны отличаться не менее чем на k . Например, если котировки равны, соответственно, 1014, 1024, 1034, 1045, 1030, 998 и k = 15 , то подпоследовательность котировок 1014, 1034, 998 является допустимой. Выбранная подпоследовательность должны быть как можно длиннее. Так, в приведенном примере выбранная последовательность не является оптимальной, подпоследовательность 1014, 1045, 1030, 998 лучше.
По заданной последовательности котировок, найдите ее длиннейшую допустимую подпоследовательность.
Первая строка входного файла содержит число n ( 1 ≤ n ≤ 100000 ) количество котировок и k ( 1 ≤ k ≤ 10 9 ). Вторая строка содержит n целых чисел последовательность котировок (все котировки находятся в интервале от 1 до 10 9 включительно).
Первая строка выходного файла должна содержать l — длину оптимальной подпоследовательности. Вторая строка должна содержать l целых чисел элементы любой такой подпоследовательности.
6 15 1014 1024 1034 1045 1030 998
4 1014 1045 1030 998