Question

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

Answer 1

Ответ:

N = int(input())

X = [''] * N

for a in range(N):

   X[a] = int(input())

a = 0

c, b, e, f = 0, 0, 0, N + 1

g, h = 0, 0

while a < N - 2:

   a += 1

   e += 1

   b, c = X[a], b

   if c < b:

       while a < N - 1:

           a += 1

           e += 1

           d = X[a]

           if d < b:

               if e < f:

                   g, h = a - e + 1, a + 1

                   f = e

               break

           elif d == b:

               continue

           else:

               break

   e = 0

if g == 0 and h == 0:

   print(0)

else: print(g, h)

Объяснение:

55 балов

Answer 2

Для решения этой задачи, вам потребуется пройтись по высотам опор входных данных и найти участки, которые соответствуют требованиям "горки" (то есть участки, на которых есть точка, строго выше начала и конца этого участка). Вам нужно будет проверить, начиная с каждой опоры, образуется ли на данном участке "горка".

Давайте рассмотрим алгоритм для решения этой задачи:

1. Считать количество опор N.
2. Считать высоты опор и сохранить их в массив.
3. Инициализировать переменные start и end для отслеживания текущего участка.
4. Инициализировать переменные max_slope и max_start для отслеживания лучшего участка "горки".
5. Пройтись по всем опорам от начала к концу: a. Если высота следующей опоры больше высоты текущей опоры, увеличить end. b. Если высота следующей опоры меньше высоты текущей опоры, проверить, образуется ли на текущем участке "горка":
   • Если образуется, проверить длину участка и обновить max_slope и max_start при необходимости.
   • Сбросить start и end для начала нового участка.
6. После прохода по всем опорам, проверить, была ли найдена подходящая "горка" (max_slope > 0). Если да, вывести max_start и max_start + max_slope - 1. Если нет, вывести 0.

Пример кода на Python:

pythonCopy code
N = int(input())
heights = [int(input()) for _ in range(N)]

start = 0
end = 0
max_slope = 0
max_start = 0

for i in range(1, N):
    if heights[i] > heights[i - 1]:
        end = i
    elif heights[i] < heights[i - 1]:
        if end - start > max_slope:
            max_slope = end - start
            max_start = start
        start = i
        end = i

if max_slope > 0:
    print(max_start + 1, max_start + max_slope)
else:
    print(0)

Этот код должен помочь вам найти подходящий участок минимальной длины, удовлетворяющий условию "горки".