АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

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

Ограничение времени: 2 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Даны N целых чисел x1, x2, ..., xN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Исходные данные

Первая строка входных данных содержит натуральное число N. Во второй строке записаны N чисел, разделенные пробелом. (N ≤ 105, 0 ≤ xi ≤ 109)

Результат

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

Пример

Исходные данныеРезультат
7
4 8 5 1 7 2 7
3
4 5 7
4
4 3 2 1
1
4 

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамическое прогр-е, рекуррентные соотношения /
12. Быстрое питание 1717. 67. Восстановление скобок 14. Выражение 2. Дерево поиска
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Динамическое программирование /
14. 06 - Выражение 1717. 870. 08 - Куча камней - 2 901. 09 - Коробки 10. 10 - Упаковка
 
время генерации 0.203 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.