Пушешников
5 год назад
Для пополнения бюджета в стране Авалон, известной своими горными
туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное
расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению,
совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток.
Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным,
он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута.
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при
передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния.
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска. Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток.
Все числа натуральные, не превосходящие 105. Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего условиям, не существует, программа должна вывести одно число 0.
ОТВЕТЫ
Леонардович
Aug 11, 2019
//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]lt;ar[j] then
begin
for k:=j+1 to n do
if ar[j]gt;ar[k] then
begin
b:=true;
if mingt;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
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]lt;ar[j] then
begin
for k:=j+1 to n do
if ar[j]gt;ar[k] then
begin
b:=true;
if mingt;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
137
Смежные вопросы:
