Для пополнения бюджета в стране Авалон, известной своими горными
туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное
расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению,
совершённому туристической группой. Кроме того, в силу старинного обычая все

туристические группы должны перемещаться по горам Авалона строго с запада на восток.
Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным,
он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута.

Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при
передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния.
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска. Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток.
Все числа натуральные, не превосходящие 105. Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего условиям, не существует, программа должна вывести одно число 0.
Please enter comments
Please enter your name.
Please enter the correct email address.
You must agree before submitting.

Answers & Comments


Copyright © 2024 SCHOLAR.TIPS - All rights reserved.