Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/18: Рейтинг темы: голосов - 18, средняя оценка - 4.83
7 / 7 / 0
Регистрация: 29.01.2022
Сообщений: 55

Решение задачи: "Долины и Холмы"

29.01.2022, 20:13. Показов 3802. Ответов 5
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вот такое условие:

Рассмотрим числовую последовательность a1, ..., aN. Мы будем называть подстроку ai, …, aj, ..., ak (1 ≤ i < j < k ≤ N) исходной последовательности холмом, если at < at+1 для любого i ≤ t < j и at > a t+1 для любого j ≤ t < k. В таком случае вершиной холма считается min{j − i, k − j} . Аналогично, мы будем называть подстроку долиной, если at > at+1 для любого i ≤ t < j и at < at+1 для любого j ≤ t < k. Тогда глубиной долины будет считаться min{j-i, k-j}. Вычислите высоту самого высокого холма и глубину самой глубокой долины в данной последовательности.

Входные данные
В первой строке входного файла находится число T (1 ≤ T ≤ 100000) — количество тестовых блоков. Далее располагаются тестовые блоки, занимающие по 2 строки. Первая из двух строк содержит целое число N (1 ≤ N ≤ 1000000), во второй строке находятся члены последовательности, разделенные пробелом. Сумма значений N всех тестовых блоков в файле не превышает 100 000. Абсолютные значения членов последовательности не превышают 1 000 000.

Выходные данные
Выходной файл должен состоять из T строк, в каждой строке по 2 числа: высота высочайшего холма и глубина самой глубокой долины. Если в тестовом блоке не существует долин или холмов, выведите число 0.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.01.2022, 20:13
Ответы с готовыми решениями:

Долины и холмы
Рассмотрим числовую последовательность a1, ..., aN. Мы будем называть подстроку ai, …, aj, ..., ak (1 ≤ i &lt; j &lt; k ≤ N) исходной...

Пираты силиконовой долины
Кто нибудь смотрел, можно узнать ваше мнение?

Найти решение уравнения, изоклинную и интегральную кривые, решение задачи Коши
Помогите пожалуйста! а) Найти решение вида: x=a,y=b,y=kx+b y'=\frac{y^2-4}{xy},\\ y'=x-y+2 б) Какая кривая является одновременно...

5
51 / 35 / 17
Регистрация: 10.01.2022
Сообщений: 110
29.01.2022, 20:16
Зачем еще раз?
0
7 / 7 / 0
Регистрация: 29.01.2022
Сообщений: 55
29.01.2022, 21:15  [ТС]
Что еще раз?

Добавлено через 6 минут
Случайно. Я просто первый раз. С механиками не разобрался.
0
-6 / 2 / 0
Регистрация: 25.01.2022
Сообщений: 10
29.01.2022, 21:29
Такое ощущение как будто я полный стажер стажера джуна(((

Добавлено через 1 минуту
ты по ходу Data Scientist ?
0
7 / 7 / 0
Регистрация: 29.01.2022
Сообщений: 55
29.01.2022, 21:31  [ТС]
Так, хватит издеваться. Я все понял.
Что по решению?
0
3750 / 1944 / 612
Регистрация: 21.11.2021
Сообщений: 3,706
30.01.2022, 06:43
Лучший ответ Сообщение было отмечено Arseniy_Ch как решение

Решение

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def get_holm_dol(diff):
    holm_max = float('-inf')
    dol_max = float('-inf')
    res = []
    i = 0
    while i < len( diff ):
        if diff[i] == 0:
            while i < len(diff) and diff[i] == 0:
                i += 1
            res.append(0)
            continue
        if diff[i] > 0:
            pos_counter = 0
            while i < len(diff) and diff[i] > 0:
                pos_counter += 1
                i += 1
            if len(res) and res[-1] < 0:
                dol_cur = min( abs(res[-1]), pos_counter )
                dol_max = max( dol_max, dol_cur )
            res.append( pos_counter )
            continue
        if diff[i] < 0:
            neg_counter = 0
            while i < len(diff) and diff[i] < 0:
                neg_counter += 1
                i += 1
            if len(res) and res[-1] > 0:
                holm_cur = min( res[-1], neg_counter )
                holm_max = max( holm_max, holm_cur )
            res.append( -neg_counter )
            continue
    if holm_max == float('-inf'):
        holm_max = 0
    if dol_max == float('-inf'):
        dol_max = 0
    return holm_max, dol_max
#==============================================================================
n = int( input( 'n = ' ) )
arr = list( int(x) for x in input( 'arr = ' ).split() )
arr.insert(0, arr[0])
arr.append(arr[-1])
diff = [ arr[i] - arr[i-1] for i in range( 1, len(arr) ) ]
print( *get_holm_dol( diff ) )
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
30.01.2022, 06:43
Помогаю со студенческими работами здесь

задачи с двумерным массивом, решение должно быть похоже на решение 8-ми классника
Без рандома, все вводится с клавиатуры, без Inc, без Break и т.д. 1)Сколько учеников не имеет в году задолженностей? 2)Распечатать...

Аналитическое решение решение краевой задачи для ОДУ второго порядка
Здравствуйте! Задача: Аналитически найти частное решение ОДУ. Изначально в частных производных, но это оду(если я неправ поправьте!) ...

Решение задачи.В чем ошибка в программе? Может неправильное решение
адача:Дано натуральное число N. Найти сумму цифр этого числа. Указание. Для выделения последней цифры целого числа N можно использовать...

Найдите общее решение и решение задачи Коши для ОДУ
Найдите общее решение и решение задачи Коши для ОДУ (с разделяющимися переменными, с однородной правой частью, или сводящееся к ним) : (1...

Найти общее решение или решение задачи Коши
вот пример:


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизита табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru