Задача 4. Американские горки Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
Аттракцион “Американские горки” представляет собой рельсовый трек, размещённый на опорах. Известна высота каждой опоры. Для рекламы аттракциона необходимо выделить один из его
фрагментов (несколько подряд идущих опор с рельсовым треком) световой подсветкой. При этом
необходимо выделить такой фрагмент трека, на котором была бы “горка” то есть на выделенном
участке трека была бы точка, которая находилась бы строго выше начала и строго выше конца
выделенного фрагмента трека.
Владелец аттракциона для экономии хочет найти подходящий участок минимальной длины,
удовлетворяющий условию наличию “горки” на этом участке.
Формат входных данных
Первая строка входных данных содержит число N — количество опор аттракциона. Следующие
N строк содержат информацию о высотах опор при движении от начала к концу аттракциона. Все
числа натуральные, не превосходящие 105
.
Формат выходных данных
Программа должна вывести два числа — номер первой и последней подходящей опоры. Опоры
нумеруются числами от 1 до N. Если фрагмента, удовлетворяющего условиям, не существует, программа должна вывести одно число 0. Если подходящих ответов несколько, нужно вывести любой
из них.
Система оценивания
Решение, правильно работающее только для случаев, когда все входные числа не превосходят
100, будет оцениваться в
В будет оцениваться решение, правильно работающее, когда все числа не превосходят 105
.
Примеры
стандартный ввод стандартный вывод
7
18
10
15
20
20
10
3
3 6
3
9
8
5
0
Пояснения к примерам
Пояснение к первому примеру. Дано 7 опор с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий
участок, содержащий “горку” — это 15, 20, 20, 10. Он начинается опорой номер 3 и заканчивается
опорой номер 6.
Пояснение ко второму примеру. Высоты опор убывают, поэтому участка с “горкой” нет.
б) остальные неизвестные величины выразить через х
в) составить формулу функции, минимальное( максимальное ) значение которой в задаче имеется.
г) исследовaть её на min (max)
Пусть разговор идёт про точку М. Её координаты буду х и (6 - х)
Расстoяние от начала координат =|ОМ|. Именно ОМ должно быть минимальным. ОМ является функцией от х. Надо ОМ найти. Будем искать по т.Пифагора.
ОМ² = х² + (6 - х)² ⇒ ОМ = √(х² + 36 -12х +х²) = √(2х² -12х + 36)
Значит, у = √(2х² -12х + 36)
Проведём исследование этой функции на min
Производная = 1/2√(2х² -12х + 36) · ( 4х - 12)
Приравниваем её к нулю. Ищем критические точки
1/2√(2х² -12х + 36) · ( 4х - 12) = 0⇒ 4х - 12 = 0⇒ 4х = 12⇒х = 3
(2х² -12х + 36≠0)
-∞ - 3 + +∞
Смотрим знаки производной слева от 3 и справа
Производная меняет свой знак с " - " на " + " ⇒ х = 3 - это точка минимума.
ответ: точка М имеет координаты (3;3), ОМ = √(9 + 9) = √18 = 3√2
Eps = 0.01;
A = -100;
B = 100;
N = 10;
Var
i : Byte;
m : array[1..N] of Real;
Flag: Boolean;
Begin
Flag:=True;
For i:=1 to N do
Begin
Repeat
Write('Введите число № ',i,' : '); Readln(m[i]);
Until (m[i]>=A) and (m[i]<=B);
end;
Writeln;
For i:=2 to N do
If abs(m[i-1]-m[i])<Eps then
Begin
Writeln(m[i-1],' ',m[i]);
Flag:=False;
end;
If Flag then Writeln('НЕТ');
end.
Результат:
Введите число № 1 : 2.3
Введите число № 2 : 2.4
Введите число № 3 : 2.45
Введите число № 4 : 2.46
Введите число № 5 : 2.465
Введите число № 6 : 3.0
Введите число № 7 : 4.0
Введите число № 8 : 4.01
Введите число № 9 : 4.005
Введите число № 10 : 4.007
2.45 2.46
2.46 2.465
4 4.01
4.01 4.005
4.005 4.007