Question

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка, которая находится строго выше начала и конца маршрута. Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска. Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 105. Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего условиям, не существует, программа должна вывести одно число 0.

Answer 1

//PascalABC.NET 3.2 сборка 1318

Var
  ar:array of byte;
  i,j,resi,resk,n,k,min:integer; 
b:boolean;
begin
b:=false;
readln(n);
min:=n+10;
setlength(ar,n+1);
for i:=1 to n do
  readln(ar[i]);
for i:=1 to n-2 do
  begin
    for j:=i+1 to n-1 do
      if ar[i]<ar[j] then
      begin
        for k:=j+1 to n do
          if ar[j]>ar[k] then
            begin
              b:=true;
                if min>k-i then
                  begin
                    resi:=i;
                    resk:=k;
                    min:=k-i;
                  end;
            end;
        end;
 end;
if b then write(resi,' ',resk) else write('0');
end.

Пример ввода:
5
1
2
3
4
3
Пример вывода:
3 5