Подразделы

Другие разделы

Дата и время

09/04/2025 08:10:08

Авторизация

Динамическое программирование

And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи

Возрастающая подпоследовательность

Ограничения: время – 100ms/1s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

Даны

$N$ целых чисел

$X_1,\ X_2,\ …,\ X_N$ . Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Ограничения:

$1\ ≤\ N\ ≤\ 10\ 000,\ 1\ ≤\ X_i\ ≤\ 60\ 000$ .

Ввод

В первой строке находится число

$N$ . В следующей строке –

$N$ чисел через пробел.

Вывод

В первой строке выводится количество невычеркнутых чисел, во второй – сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.

Пример ввода

6
2 5 3 4 6 1

Пример вывода

4
2 3 4 6