Списки: частичные суммы, два указателя

Сюжет 1: частичные суммы

A: Суммы на префиксах

Дано $N$ чисел. Для каждого $k=1, ..., N$ выведите сумму первых $k$ данных чисел.

Первая строка содержит число $N\le 10^5$. Следующие $N$ строк содержат по одному числу.

Программа должна вывести $N$ чисел, $k$-е из данных чисел должно равняться сумме первых $k$ данных чисел.

Ввод	Вывод
4 1 1 2 2	1 2 4 6

B: Час пик - 2

Не без вашей помощи в метро посчитали количество пассажиров в каждый час работы метро. Теперь вас просят по этим данным найти “час пик” такие $k$ подряд идущих часов, что суммарное число пассажиров в эти часы максимальное.

Первая строка входных данных содержит количество часов в сутках, в течение которых работает метрополитен $N$ ($1\le N\le 10^5$). Вторая строка содержит $N$ неотрицательных чисел, записанных через пробел количество пассажиров в каждый из часов. В третьей строке записана продолжительность часа пик $K$ ($1\le k \le N$).

Найдите $K$ подряд идущих часов работы метрополитена с максимальным суммарным числом пассажиров и выведите суммарное число пассажиров за эти часы.

Алгоритм должен иметь сложность $O(N)$.

Ввод	Вывод
7 3 2 5 4 3 2 4 3	12

C: Range Sum Query

Дано $N$ чисел и $M$ запросов вида $(i, j)$. Для каждого запроса выведите сумму всех данных чисел начиная от $i$-го до $j$-го (включительно).

Первая строка содержит число $N\le 10^5$. Вторая строка содержит $N$ исходных чисел. Третья строка содержит количество запросом $M\le 10^5$. Следующие $M$ строк содержат по два числа $i$ и $j$: $1\le i \le j \le N$.

Программа должна вывести $M$ чисел: ответы на данные запросы.

Алгоритм должен иметь сложность $O(N + M)$.

Ввод	Вывод
4 1 2 3 4 3 2 3 1 4 1 1	5 10 1

D: Максимальная непрерывная сумма за $O(n^2)$

В массиве из $n$ элементов, заполненном произвольными целыми числами, найдите непрерывный фрагмент, сумма чисел в котором максимальна, то есть найдите такие i и j, что сумма A[i]+A[i+1]+...+A[j] максимальна.

Первая строка входных данных содержит значение $n$, во второй строке записаные $n$ целых чисел.

Программа должна вывести два индекса i и j таких, что сумма элементов от i-го до j-го (включительно) максимальна. Если таких пар несколько, то выведите ту пару, у которой j минимально возможное, а при равных j выведите ту пару, у которой i максимально возможно.

В этой задаче $n\le 1000$ и решение должно иметь сложность $O(n^2)$.

Ввод	Вывод
5 -1 2 3 -2 2	1 2
7 2 -2 3 -1 5 -2 7	2 6

E: Максимальная непрерывная сумма за $O(n)$

Решите предыдущую задачу за $O(n)$. Ограничение: $n\le 10^5$.

F: Прямоугольные префиксы

Для решения этой задачи нужно что-то знать о двумерных массивах.

Дана прямоугольная матрица (таблица чисел), содержащая $N$ строк и $M$ столбцов.

Для каждого элемента этой матрицы вычислите сумму всех чисел, находящихся левее и выше данного числа, то есть сумму чисел, которые находятся внутри прямоугольника, правый нижний угол которого является данным числом.

Программа получает на вход два числа $N$ и $M$. Следующие $N$ строк содержат по $M$ целых неотрицательных чисел от 0 до 1000 каждое.

Программа должна вывести другую прямоугольную матрицу, также содержащую $N$ строк и $M$ чисел в каждой строке, построеной по описанномы выше правилу.

Решение должно иметь сложность $O(NM)$. Ограничения: $NM\le 50\,000$.

Ввод	Вывод
3 4 1 2 1 2 2 1 2 1 1 2 1 2	1 3 4 6 3 6 9 12 4 9 13 18

G: RSQ на прямоугольниках

Для решения этой задачи нужно что-то знать о двумерных массивах.

Дана прямоугольная матрица (таблица чисел), содержащая $N$ строк и $M$ столбцов. Строки пронумеруем числами от 1 до $N$ сверху вниз, столбцы пронумеруем числами от 1 до $M$ слева направо. Рассмотрим какой-либо прямоугольник внутри данной матрицы. Пусть $(x_1, y_1)$ — координаты его левого верхнего угла (то есть номер строки и номер столбца клетки, которая является левой верхней клеткой), $(x_2, y_2)$ — координаты его правого нижнего угла.

Научитесь быстро вычислять сумму всех чисел внутри произвольного такого прямоугольника.

Программа получает на вход три числа $N$, $M$, $K$. Следующие $N$ строк содержат по $M$ целых неотрицательных чисел от 0 до 1000 каждое. Следующие $K$ строк содержат по одному запросу на вычисление суммы: четыре числа $x_1$, $y_1$, $x_2$, $y_2$ ($1\le x_1\le x_2\le N$, $1\le y_1\le y_2\le M$).

Программа должна вывести $K$ целых чисел: ответы на все запросы.

Решение должно иметь сложность $O(NM+K)$. Ограничения: $NM\le 50\,000$, $K\le 50\,000$.

Ввод	Вывод
3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3	28 21

Сюжет 2: два указателя

H: Субботник - минимальное неудобство

Напомним условия задачи про субботник. Есть $N$ человек, одно бревно переносит бригада из $K$ человек. Неудобством бригады является разность роста самого высокого и самого низкого члена бригады.

Даны значения роста $N$ человек и размер бригады $K$. Определите наименьшее возможное неудобство бригады, которую можно сформировать.

Программа получает на вход числа $N$ и $K$ ($1\le K\le N\le 10^5$) в первой строке, во второй строке записано $N$ натуральных чисел через пробел — значения роста.

Программа должна вывести одно целое число: минимальное значение неудобства бригады.

Ввод	Вывод
6 3 6 1 7 9 3 5	2

I: Субботник - максимальный размер бригады

По правилам безопасности максимальное неудобство в бригаде не должно превышать значения $M$, а количество людей в бригаде может быть произвольным.

Определите максимальный размер бригады (чем больше людей в бригаде, тем легче носить брёвна!), неудобство которой не превышает $M$.

Программа получает на вход числа $N$ и $M$ в первой строке ($1\le N\le 10^5$, $M\ge 0$), во второй строке записано $N$ натуральных чисел через пробел — значения роста.

Программа должна вывести одно целое число: максимальное число людей в бригаде, неудобство которой не превосходит $M$.

Указание. Это типичная задача на метод двух указателей. Отсортируем массив и будем перебирать индекс члена бригады с наименьшим ростом. В другой переменной будем хранить индекс члена бригады с наибольшим ростом, которого можно поставить к выбранном члену бригады с наименьшим ростом. Когда индекс члена бригады с наименьшим ростом увеличивается, индекс члена бригады с наибольшим ростом также увеличивается. Решение имеет сложность сортировки + $O(N)$.

Ввод	Вывод
6 3 6 1 7 9 3 5	3

J: Субботник - максимальное число бригад

Каждая бригада должна содержать ровно $K$ человек, а неудобство бригады не должно превышать значения $M$. Определите наибольшее число бригад, которое можно составить при таких условиях.

Программа получает на вход числа $N$, $K$ и $M$ в первой строке ($1\le K \le N\le 10^5$, $M\ge 0$), во второй строке записано $N$ натуральных чисел через пробел — значения роста.

Программа должна вывести одно целое число: максимальное количество бригад, которое можно составить из данных людей.

Ввод	Вывод
10 3 3 9 1 10 3 12 4 14 5 16 7	2

K: Дюбели и сверла

Для того, чтобы повесить картину на стенку, нужно просверлить в стене дырку, вбить в неё дюбель и вкрутить в него саморез. Есть $N$ сверел и $M$ дюбелей, нужно найти среди них сверло и дюбель одинакового радиуса. Если таких нет, то нужно найти такое сверло и дюбель, чтобы разность их диаметров была как можно меньше (по модулю).

В первой строке входных данных заданы два числа $N$ и $M$ ($1\le N, M\le 10^5$). Во второй строке заданы $N$ целых чисел — диаметры сверел. В третьей строке заданы $M$ целых чисел — диаметры дюбелей. Диаметры заданы в неубывающем порядке, значения диаметров не превосходят $10^9$.

Программа должна вывести одно целое число — минимальное значение модуля разности диаметров сверла и дюбеля.

Ввод	Вывод
3 2 1 8 15 5 6	2
3 3 1 3 5 3 4 6	0

L: Грузовики

Дано $N$ грузов. Для их перевозки можно заказать $M$ одинаковых грузовиков, причем на каждый грузовик можно погрузить не более 2 любых грузов. Определите минимально возможную грузоподъемность одного грузовика, при которой можно увезти все грузы на $M$ грузовиках.

Первая строка входных данных содержит два числа $N$ и $M$ ($1\le N, M\le 10^5$). Во второй строке заданы $N$ целых чисел — массы грузов (натуральные числа, не превосходящие $10^9$).

Программа должна вывести одно число — минимально возможную грузоподъемность грузовика. Если увезти данные грузы на $M$ грузовиках невозможно, программа должна вывести число -1.

Ввод	Вывод
5 4 3 5 3 7 5	7
5 3 3 5 3 7 5	8

M: Подобрать сумму

Дано $N$ различных целых чисел и целое число $Q$. Выберите среди данных чисел два числа таких, чтобы их сумма была как можно ближе к $Q$.

Первая строка входных данных содержит числа $N$ и $Q$ ($2\le N\le 10^5$, $1\le Q\le 10^9$). Во второй строке записано $N$ натуральных чисел, не превосходящих $10^9$, все числа различные.

Программа должна вывести два числа из данных.

Ввод	Вывод
5 10 1 5 8 2 6	2 8
3 10 5 8 6	6 5

N: Калитка в заборе

Забор представляет собой отрезок прямой, левый конец которого имеет координату $L$, правый конец — координату $R$. На этом отрезке вкопано $N$ столбов.

Необходимо выкопать наименьшее число столбов так, чтобы в заборе можно было сделать проход, шириной не менее, чем $W$. После выкавывания столбов должен найтись промежуток между двумя какими-то оставшимися столбами, или между между оставшимся столбом и концом забора, или между двумя концами забора шириной не менее $W$, не содержащий других столбов.

Первая строка содержит два целых числа $N$ и $W$ — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что $0\le N\le 30000$ и что $1\le W\le 60000$.

Во второй строке даны два числа $L$ и $R$ — координаты левого и правого конца забора ($-30000\le L\lt R\le 30000$). Третья строка содержит $N$ чисел — координаты вкопанных столбов, расположенные строго на отрезке $[L, R]$. Все координаты, включая $L$ и $R$ — различные целые числа.

Программа должна вывести минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.

Если решений несколько, то нужно вывести любое из них. Если решения нет, то нужно вывести одно число -1.

Ввод	Вывод
3 2 2 6 3 4 5	1 2
3 2 1 6 4 3 5	0
3 5 1 7 5 3 4	3 2 1 3

O: Сплоченная команда

Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).

Ваша задача состоит в том, чтобы помочь сделать правильный выбор из $N$ человек, для каждого из которых известен его ПП.

В первой строке входных данных записано целое число $N$ ($0\le N\le 30000$). В последующих $N$ строках записано по одному целому числу $P_i$ ($0\le P_i\le 60000$), представляющему собой ПП соответствующего игрока.

В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входных данных. Если ответов несколько, выведите любой из них.

Ввод	Вывод
4 1 5 3 3	3 11 3 4 2
5 100 20 20 20 20	2 120 2 1

P: Поиск в трех списках

Даны три списка чисел, упорядоченных по неубыванию. Известно, что некоторое число встречается в каждом из этих списков. Найдите это число, не используя дополнительных массивов.

Алгоритм должен иметь сложность $O(n+m+k)$, где $n$, $m$, $k$ — длины данных списков.

Программа получает на вход три списка, заданных как в предыдщущих задачах.

Программа должна вывести одно число, которое встречается в каждом из этих списков. Если таких чисел несколько, нужно вывести любое из них.

Ввод	Вывод
5 2 4 4 6 7 3 1 4 8 4 1 2 3 4	4

Сюжет 3: подсчет количества вариантов

Q: Субботник - число способов выбрать двух человек

Для переноски бревна нужно выбрать двух человек, разница в росте которых не превышает $M$.

Даны значения роста $N$ человек. Определите количество способов выбрать двоих из них так, чтобы разница их роста была не больше $M$.

Программа должна вывести одно целое число — искомое количество способов.

Ввод	Вывод
4 2 1 4 3 5	4

R: Бинарные подстроки

Дана строка, состоящая только из символов “0” и “1”. Найдите количество непустых подстрок данной строки, содержащих ровно $k$ единиц.

Первая строка входных данных содержит целое число $k$ ($0\le k\le 10^6$). Во второй строке записана непустая строка $s$, длина которой не превосходит $10^6$ символов.

Программа должна вывести одно целое число — количество подстрок данной строки, содержащих ровно $k$ единиц.

Ввод	Вывод
1 1010	6

S: Заполнить пропуски

Дана строка длиной не более $10^6$ символов, содержащая только строчные латинские буквы и знаки вопроса. Определите, сколько существует подстрок данной строки, которые при некоторой замены знаков вопроса все буквы были бы одинаковыми.

Ввод	Вывод
ab?c	6
aa??b?c	19

Объяснение первого примера. Описанному условию отвечают четыре подстроки из одного символа, подстрока b? и подстрока ?c.

Разные задачи

T: Составить треугольник

Даны $N$ отрезков. Определите, сколькими способами можно выбрать из них три отрезка так, чтобы из них можно было составить невырожденный треугольник. Решение должно иметь сложность $O(n^2)$.

Первая строка входных данных содержит число $N$ ($1\le N\le 3000$). Во второй строке записано $N$ натуральных чисел не превосходящих $10^9$ — длины отрезков.

Программа должна вывести единственное число: искомое количество способов.

Ввод	Вывод
4 3 1 3 5	2

U: Аллея

Аллея состоит из $N$ посаженных в один ряд деревьев, каждое одного из $K$ видов. Решено было вырубить аллею, но сохранив при этом часть деревьев. Деревья, которые не будут вырублены, должны идти подряд, причем должно остаться хотя бы по одному дереву каждого из $K$ видов. Определите, какое наименьшее число деревьев необходимо сохранить.

В первой строке входных данных даны два числа $N$ и $K$ ($1 \le K\le N \le 250000$). Во второй строке записаны $N$ чисел, $i$-е число второй строки задает вид $i$-го дерева аллеи. Гарантируется, что присутствует хотя бы одно дерево каждого цвета.

Программа должна вывести два числа: номер первого и последнего дерева, которые нужно оставить на аллее. Если ответов несколько, выведите любой из них.

Ввод	Вывод
5 3 1 2 1 3 2	2 4
6 4 2 4 2 3 3 1	2 6

V: Дома и магазины – 2

На Новом проспекте построили подряд $N$ зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

Но оказалось, что жителям некоторых домов на Новом проспекте слишком далеко приходится идти до ближайшего магазина. Для разработки плана развития общественного транспорта на Новом проспекте мэр города попросил вас выяснить, какое же наибольшее расстояние приходится преодолевать жителям Нового проспекта, чтобы дойти от своего дома до ближайшего магазина.

Первая строка входных данных содержит количество домов на Новом проспекте $N$, $N\le 10^5$. Вторая строка содержит $N$ чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.

Ввод	Вывод
10 2 0 1 1 0 1 0 2 1 2	3