Районная олимпиада 2019-2020 информатика
Задача E. Второй максимум
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам дана последовательность $a_1, a_2...a_n$ длины $n$. Для каждого $k$ от $2$ до $n$ найдите значение второго по величине элемента среди первых $k$ элементов последовательности $a$.
Формат входного файла
В первой строке одно целое число $n$ $(1 <= n <= 10^5)$.
Во второй строке $n$ целых чисел $a_1, a_2... a_n$ $(1 <= a_i <= 10^9)$.
Формат выходного файла
Выведите ответ для каждого $k$ от $2$ до $n$.
Система оценки
Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:
- $1 <= n <= 100$. Тесты с номерами 1-3.
- $1 <= n <= 5000$. Тесты с номерами 4-6.
- $1 <= n <= 10^5$. Тесты с номерами 7-10.
Пример:
Вход 7 1 2 3 3 7 5 6Ответ
1 2 3 3 5 6
Замечание
В примере:
- $k=2$. Первые $k$ чисел $\underline{1}, 2$. Ответ $1$
- $k=3$. Первые $k$ чисел $1, \underline{2}, 3$. Ответ $2$
- $k=4$. Первые $k$ чисел $1, 2, \underline{3}, 3$. Ответ $3$
- $k=5$. Первые $k$ чисел $1, 2, \underline{3}, 3, 7$. Ответ $3$
- $k=6$. Первые $k$ чисел $1, 2, 3, 3, 7, \underline{5}$. Ответ $5$
- $k=7$. Первые $k$ чисел $1, 2, 3, 3, 7, 5, \underline{6}$. Ответ $6$
Комментарий/решение:
n = int(input()) # Ввод числа n
array = list(map(int, input().split())) # Ввод списка через запятую
for k in range(2, n+1): # проход по всем отрезкам от 1 до n
temporary = array[:k]# временный список равен срезу последних k эл-ов
temporary.remove(max(temporary)) # Убираем максимальный эл-нт из списка
print(max(temporary), end=" ") # Вывод второго максимального эл-а, в строку через пробел
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.