2026/27, Кружок для начинающих, Линейные алгоритмы
A: Максимальная разность
Задана последовательность из \(n\) целых чисел. Необходимо найти два таких элемента, что разность между правым и левым значениями будет максимальна.
Формат входных данных
В первой строке задано натуральное число \(n\) — количество элементов в последовательности (\(2 \leq n \leq 10^5\)).
В следующей строке заданы \(n\) целых чисел через пробел — элементы последовательности \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^9\)).
Формат выходных данных
В первой строке выведите два числа \(i\) и \(j\) (\(i < j\)) — номера элементов \(a_i\) и \(a_j\) в последовательности такие, что \(a_j - a_i\) максимально.
Во второй строке выведите саму максимальную разность \(a_j - a_i\).
Если подходящих пар несколько, выведите любую из них.
Пример
| Ввод | Вывод |
|---|
5
1 3 8 -2 3
|
1 3
7
|
B: Максимальная разность - 2
Задана последовательность из \(n\) целых чисел. Необходимо найти два таких элемента, что разность между правым и левым значениями будет максимальна, при этом между ними находится не менее, чем \(k\) элементов.
Формат входных данных
В первой строке задано натуральное число \(n\) — количество элементов в последовательности (\(3 \leq n \leq 10^5\)).
Во второй строке задано число \(k\) (\(1 \leq k \leq 10\)). Гарантируется, что \(n \geq k + 2\), то есть хотя бы одна подходящая пара существует.
В третьей строке заданы \(n\) целых чисел через пробел — элементы последовательности \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^9\)).
Формат выходных данных
В первой строке выведите два числа \(i\) и \(j\) (\(i < j\)) — номера элементов \(a_i\) и \(a_j\) в последовательности такие, что \(a_j - a_i\) максимально, при этом между \(a_i\) и \(a_j\) должно быть не менее чем \(k\) элементов, то есть \(j - i - 1 \geq k\).
Во второй строке выведите саму максимальную разность \(a_j - a_i\).
Если есть несколько одинаковых пар, то выведите любую.
Примеры
| Ввод | Вывод |
|---|
6
2
1 3 8 -2 3 15
|
1 6
14
|
7
2
-1 -2 -3 -4 -5 -6 -7
|
1 4
-3
|
C: Максимальная сумма
Задана последовательность из \(n\) целых чисел. В этой последовательности найдите непрерывный подотрезок, сумма чисел в котором максимальна.
Фактически требуется найти такие \(i\) и \(j\) (\(i \leq j\)), что сумма всех элементов массива от \(a_i\) до \(a_j\) включительно будет максимальна.
Формат входных данных
В первой строке задано натуральное число \(n\) — количество элементов в последовательности (\(2 \leq n \leq 10^5\)).
В следующей строке заданы \(n\) целых чисел через пробел — элементы последовательности \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10^9\)).
Формат выходных данных
Выведите через пробел пару искомых значений индексов \(i\) и \(j\). Если таких пар несколько, то \(j\) должно быть минимально возможным, а при равных \(j\) значение \(i\) должно быть максимально возможным.
Пример
| Ввод | Вывод |
|---|
7
1 2 -3 5 2 8 1
|
4 7
|
D: Минимум в окне
Рассмотрим последовательность целых чисел длины \(N\). По ней с шагом 1 двигается “окно” длины \(K\), то есть сначала в “окне” видно первые \(K\) чисел, на следующем шаге в “окне” уже будут находиться \(K\) чисел, начиная со
второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.
Формат входных данных
В первой строке входных данных содержатся два числа \(N\) и \(K\) \((1 \leq N \leq 150000, 1 \leq K \leq 10000, K \leq N)\) – длины последовательности
и “окна”, соответственно. На следующей строке находятся \(N\) чисел – сама последовательность.
Формат выходных данных
Выходые данные должны содержать \(N − K + 1\) строк – минимумы для каждого положения “окна”.
Пример
| Ввод | Вывод |
|---|
7 3
1 3 2 4 5 3 1
|
1
2
2
3
1
|
E: Великое Лайнландское переселение
Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором распологаются \(N\) городов, последовательно пронумерованных от \(0\) до \( N - 1 \) . Направление в сторону от первого города к нулевому названо западным, а в обратную — восточным.
Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.
Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.
Формат входных данных
В первой строке дано одно число \(N\) \(( 2 \leq N \leq 10^{5} )\) — количество городов в Лайнландии. Во второй строке дано \(N\) чисел \(a_{i} (0 \le a_{i} \le 10^{9} )\) — средняя цена проживания в городах с нулевого по \(N-1\) соответственно.
Формат выходных данных
Для каждого города в порядке с нулевого по \(N - 1\) выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите -1.
Примеры
| Ввод | Вывод |
|---|
10
1 2 3 2 1 4 2 5 3 1
|
-1 4 3 4 -1 6 9 8 9 -1
|
10
65 51 79 36 2 47 92 30 25 94
|
1 3 3 4 -1 7 7 8 -1 -1
|
F: Гистограмма
Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая
состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.
Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится
на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме.
Формат входных данных
В первой строке входного файла записано число \(N\) (\(0 \leq N \leq 10^{6}\)) - количество прямоугольников гистограммы. Затем следует \(N\) целых чисел \(h_1 ... h_n\), где \(0 \leq h_{i} \leq 10^{9}\). Эти числа обозначают высоты прямоугольников гистограммы
слева направо. Ширина каждого прямоугольника равна \(1\)
Формат выходных данных
Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.
Примеры
| Ввод | Вывод |
|---|
7 2 1 4 5 1 3 3
|
8
|
4 1000 1000 1000 1000
|
4000
|
G: Большой, белый, очень прямоугольный
В прямоугольной таблице клетки раскрашены в белый и черный цвета. Найти в ней прямоугольную область белого цвета, состоящую из наибольшего количества ячеек.
Формат входных данных
Во входном файле записана сначала высота \(N\), а затем ширина \(M\) таблицы \((1 \le N \le 5000\), \(1 \le M \le 5000)\), а затем записано \(N\) строк по \(M\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка
таблицы выкрашена в белый цвет, а \(1\) – что в черный.
Формат выходных данных
В выходной файл вывести одно число — количество клеток, содержащихся в наибольшем по площади белом прямоугольнике.
Примеры
| Ввод | Вывод |
|---|
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
|
9
|
4 4
0 0 0 0
0 1 0 1
0 0 0 0
1 1 0 0
|
4
|