Сегодня хочу поговорить о пригласительном этапе олимпиады Сириус по информатике для 8-10 классов, в частности, о задаче «Американские горки».
Напомню условие: аттракцион Американские горки представляет собой рельсовый трек, размещенный на опорах. Известна высота каждой опоры. Необходимо выделить один из его фрагментов (несколько подряд идущих опор) световой подсветкой. При этом необходимо выделить такой фрагмент, на котором была бы горка, т. е. была бы точка, которая находилась бы строго выше начала и строго выше конца выделенного фрагмента.
Необходимо найти подходящий участок минимальной длины.
Число опор и их высота не превышают 100000.
На вводе нужно задать число опор и высоту каждой опоры, на выходе - номер первой и последней опоры подходящего фрагмента. Если горок нет - вывести 0, если подходящих фрагментов несколько - вывести любой.
На видеоразборе на странице Олимпиады и в ответах горкой назван фрагмент, в котором «в середине идут элементы, равные максимальному, а перед и после идут меньшие элементы» (смотреть с момента 06:45 https://sochisirius.ru/obuchenie/distant/smena635/3096). Это уже не горка, а плато, о чем прямо сказано на видео, и противоречит условию, согласно которому нужно найти точку, расположенную СТРОГО выше начала и СТРОГО выше конца.
Опуская факт несоответствия предлагаемого решения поставленной задаче, отмечу, что решить задачу с горкой сложнее, чем найти последовательность точек с равной высотой.
Предлагаю решение на Паскале.
Объявляем переменные
var
n, i, k, n1, n2, n11, n12, l: longint;
z: array[1..100000] of longint;
Здесь n - число опор;
i, k - переменные для циклов;
n1, n2 - начало и конец текущей найденной горки;
n11, n12 - начало и конец предыдущей найденной горки;
l - признак того, что решение задачи есть. Если l=0 - горок нет.
z - массив высот опор;
Вводим исходные данные и присваиваем переменным начальные значения:
begin
readln(n);
for i:=1 to n do readln(z[i]);
n1:=0; n2:=0; n11:=1; n12:=n; l:=0;
Теперь, начиная со 2-й опоры и заканчивая предпоследней, ищем пик, т. е. точку, которая выше своих соседей:
i:=2;
while i<=(n-1) do
begin
if (z[i-1]<z[i]) and (z[i+1]<z[i]) then
Если пик найден, значит, мы имеем горку по крайне мере на трех опорах. Присваиваем номера началу и концу текущей горки:
begin
n1:=i-1; n2:=i+1;
Далее ищем левую границу горки, т. е. находим опору, до которой идет строгое снижение высоты:
for k:=i-1 downto 2 do if z[k]>z[k-1] then n1:=n1-1 else break;
Аналогично находим правую границу горки:
for k:=i+1 to n-1 do if z[k]>z[k+1] then n2:=n2+1 else break;
Таким образом, горка найдена, т. е. решение есть. Присваиваем отличное от нуля значение переменной l, а значению i присваиваем номер правой границы горки, поскольку дальнейший поиск пойдет от нее:
l:=1; i:=n2;
Теперь проверяем, является ли текущая горка короче или равной предыдущей, и если да, то предыдущие границы меняем на текущие:
if (n12-n11)>=(n2-n1) then
begin
n11:=n1; n12:=n2;
end;
Завершаем условный оператор по поиску пика и основной цикл, перейдя к следующей точке:
end;
i:=i+1;
end;
И выводим результат:
if l=0 then writeln(l) else writeln(n11,' ',n12);
end.
Полностью вся программа без комментариев:
var
n, i, k, n1, n2, n11, n12, l: longint;
z: array[1..100000] of longint;
begin
readln(n);
for i:=1 to n do readln(z[i]);
n1:=0; n2:=0; n11:=1; n12:=n; l:=0;
i:=2;
while i<=(n-1) do
begin
if (z[i-1]<z[i]) and (z[i+1]<z[i]) then
begin
n1:=i-1; n2:=i+1;
for k:=i-1 downto 2 do if z[k]>z[k-1] then n1:=n1-1 else break;
for k:=i+1 to n-1 do if z[k]>z[k+1] then n2:=n2+1 else break;
l:=1; i:=n2;
if (n12-n11)>=(n2-n1) then
begin
n11:=n1; n12:=n2;
end;
end;
i:=i+1;
end;
if l=0 then writeln(l) else writeln(n11,' ',n12);
end.
Ну что, проверим? Пусть задана конфигурация, приведенная на рисунке:
На вводе имеем 20 опор и их высоты: 2 1 5 4 3 1 3 8 8 6 6 2 4 9 5 5 7 8 6 4.
На выходе получаем два числа: 12 и 15. Это начало и конец самой короткой горки. Что и требовалось получить.
Ставьте лайки, пишите отзывы. Если тема интересная - могу написать программы на Паскале для других задач, а то Оргкомитет привёл все решения на языке Python, которым, вероятно, мало кто владеет.