Создан заказ №3969490
9 мая 2019
Задача программирование
Как заказчик описал требования к работе:
Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
На аллее перед зданием Министерства Обороны в ряд высажены
n
дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для
придания аллее более милитаристического вида.
Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:
если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб;
если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.
В частности, согласно этому правилу, нельзя срубить крайний левый и крайний правый дубы.
Министр хочет выработать такой план вырубки, чтобы в итоге осталось несколько дубов, высоты которых образуют неубывающую последовательность, то есть чтобы каждый дуб был не ниже, чем все дубы, стоящие слева от него. При этом, как человек любящий флору, министр хочет, чтобы было срублено минимальное возможное количество деревьев.
Помогите сотрудникам министерства составить оптимальный план вырубки аллеи или выяснить, что срубить дубы соответствующим образом невозможно.
Формат ввода
Первая строка входного файла содержит целое число
n
— количество дубов, растущих на аллее(2≤n≤200). Вторая строка содержит n
чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1000.
Формат вывода
Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число −1.
В случае, если искомый план существует, в первую строку выходного файла выведите целое число
m— минимальное количество дубов, которые необходимо срубить. В следующие m
строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.
Дубы нумеруются слева направо натуральными числами от
1 до n.
Если планов с наименьшим числом срубаемых дубов несколько, выведите любой из них.
c++ или java
подробнее
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
10 мая 2019
Заказ завершен, заказчик получил финальный файл с работой
5
Задача программирование.jpg
2019-05-13 01:46
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Отличный автор. Делает все быстро и качественное, в случае каких-либо проблем, всегда поможет
Хочешь такую же работу?
300 ₽
