Задача 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.
Пояснение ко второму примеру. Высоты опор убывают, поэтому участка с “горкой” нет.
Давайте рассмотрим алгоритм решения задачи:
1. Считываем количество опор аттракциона из первой строки входных данных и сохраняем в переменную N.
2. Создаем пустой список для высот опор трека.
3. Считываем N строк с информацией о высотах опор и добавляем их в список.
4. Создаем переменные start_index и end_index и инициализируем их значением None. Эти переменные будут хранить индексы начала и конца выделенного фрагмента трека.
5. Создаем переменную min_length и инициализируем ее значением бесконечности. Эта переменная будет хранить минимальную длину выделенного фрагмента трека.
6. Используем вложенный цикл для проверки всех возможных фрагментов трека. Внешний цикл перебирает возможные начальные опоры, а внутренний цикл - возможные конечные опоры.
7. Внутри вложенных циклов проверяем, есть ли "горка" на текущем фрагменте трека. Для этого сравниваем высоту текущей опоры с высотами предыдущей и следующей опор. Если высота текущей опоры больше высоты предыдущей и следующей опоры, то у нас есть "горка" на текущем фрагменте.
8. Если на текущем фрагменте есть "горка", то проверяем его длину. Если текущая длина меньше минимальной длины, то обновляем значения переменных start_index, end_index и min_length.
9. После окончания циклов, проверяем, был ли найден подходящий фрагмент трека. Если min_length все еще равна бесконечности, то выводим число 0, так как подходящего фрагмента нет. Иначе выводим значения переменных start_index и end_index, так как у нас найден подходящий фрагмент трека.
10. Завершаем программу.
На основе данного алгоритма можно написать программу на языке программирования, которая будет решать данную задачу. Вот примерный код программы на Python:
```python
N = int(input()) # Считываем количество опор
heights = [] # Создаем список для высот опор
for _ in range(N):
height = int(input()) # Считываем высоту опоры
heights.append(height) # Добавляем высоту в список
start_index = None # Индекс начальной опоры выделенного фрагмента
end_index = None # Индекс конечной опоры выделенного фрагмента
min_length = float('inf') # Минимальная длина выделенного фрагмента
for i in range(N):
for j in range(i+1, N):
if all(heights[k] < heights[k+1] for k in range(i, j)): # Проверяем наличие "горки"
length = j - i + 1 # Длина текущего фрагмента
if length < min_length: # Проверяем, является ли текущая длина минимальной
start_index = i + 1 # Обновляем начальный индекс
end_index = j + 1 # Обновляем конечный индекс
min_length = length # Обновляем минимальную длину
if min_length == float('inf'): # Проверяем, был ли найден подходящий фрагмент
print(0) # Если нет, выводим 0
else:
print(start_index, end_index) # Выводим индексы подходящего фрагмента
```
Таким образом, данная программа будет находить подходящий фрагмент трека минимальной длины, удовлетворяющий условию наличия "горки".