pgm16.2★ — Частичные суммы, два указателя

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

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

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

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

IDE

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

IDE

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)$.

5
10
1

IDE

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

IDE

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

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

IDE

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

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

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

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

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

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

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

1 3 4 6
3 6 9 12
4 9 13 18

IDE

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$.

28
21

IDE

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

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

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

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

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

6 3
6 1 7 9 3 5

IDE

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

IDE

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

IDE

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

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

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

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

3 2
1 8 15
5 6

3 3
1 3 5
3 4 6

IDE

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

5 3
3 5 3 7 5

IDE

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

IDE

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

3 5
1 7
5 3 4

3
2 1 3

IDE

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

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

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

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

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

2 120
2
1

IDE

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

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

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

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

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

IDE

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

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

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

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

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

4 2
1 4 3 5

IDE

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

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

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

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

1
1010

IDE

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

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

ab?c

aa??b?c

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

IDE

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

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

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

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

4
3 1 3 5

IDE

U: Аллея

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

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

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

5 3
1 2 1 3 2

2 4

6 4
2 4 2 3 3 1

2 6

IDE

V: Таблица

Рассмотрим прямоугольную таблицу размером $n\times m$. Занумеруем строки таблицы числами от 1 до $n$, а столбцы — числами от 1 до $m$. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через $a_{ij}$ число, стоящее на пересечении $i$-й строки и $j$-го столбца. Первая строка таблицы заполняется заданными числами $a_{11}$, $a_{12}$, ..., $a_{1m}$. Затем заполняются строки с номерами от 2 до $m$. Число $a_{ij}$ вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом $a_{ij}$. Все вычисления при этом выполняются по модулю $r$.





				a_i,j

Более точно, значение $a_{ij}$ вычисляется по следующей формуле:

\[ a_{i,j}=\left(\sum_{k=1}^{i-1}\sum_{t=\max(i-k, 1)}^{\min(i+k,m)}a_{i-k,t}\right)\bmod r \]

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

2	3	4	5
5 = 2 + 3	9 = 2 + 3 + 4	12 = 3 + 4 + 5	9 = 4 + 5
23 = 2 + 3 + 4 + 5 + 9	0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40	4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40	33 = 3 + 4 + 5 + 12 + 9

Требуется написать программу, которая по заданной первой строке таблицы $a_{11}$, $a_{12}$, ..., $a_{1m}$ вычисляет последнюю строку, как описано выше.

Первая строка входного файла содержит числа $n$, $m$, $r$ ($2 \le n, m\le 2000$, $2\le r\le 10^9$ — число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит $m$ целых неотрицательных чисел $a_{11}$, $a_{12}$, ..., $a_{1m}$, не превосходящих $10^9$ — первую строку таблицы.

Программа должна вывести числа $a_{n1}$, $a_{n2}$, ..., $a_{nm}$.

2 3 10
1 2 3

3 6 5

3 3 10
1 1 1

8 0 8

3 4 40
2 3 4 5

23 0 4 33

IDE

W: Дома и магазины — 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

IDE

Z: Беги, Форрест, беги!

Юный спортсмен Гамп собирается пробежать по дорожке, состоящей из клеток.

Бег происходит следующим образом: изначально Гамп занимает ногой на дорожке только клетки - A + 1, ..., 0, где A — длина стопы Гампа.

A = 2; до начала бега

Затем он делает шаг и занимает ногой только клетки B, ..., B - A + 1, где B — длина шага Гампа. После следующего шага он занимает только клетки 2B, ..., 2B - A + 1 и так далее. Другими словами, каждый раз занимаемая область сдвигается на B клеток вправо.

A = 2, B = 3; после первого шага

A = 2, B = 3; после второго шага

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

Гамп может отступить на любое количество клеток строго меньшее B (а может и вовсе не отступать), после чего начать забег по описанным выше правилам.

A = 2, B = 3; отступ — 2 клетки; до начала бега

A = 2, B = 3; отступ — 2 клетки; после первого шага

A = 2, B = 3; отступ — 2 клетки; после второго шага

Помогите Гампу выбрать отступ, начав с которого он наступит на минимальное количество покрашенных клеток.

Входные данные

В первой строке содержатся два целых числа A и B — длины стопы и шага Гампа соответственно (1 ⩽ A ⩽ B ⩽ 200 000).

Во второй строке содержится единственное целое число N — количество покрашенных клеток (1 ⩽ N ⩽ 200 000).

В третьей строке содержатся N целых чисел — номера покрашенных клеток в возрастающем порядке. Все номера не меньше 1 и не превосходят 10⁹.

Входные данные

Выведите два числа — на сколько клеток нужно отступить Гампу, чтобы наступить на минимально возможное количество покрашенных клеток, и это количество соответственно.

Если правильных ответов несколько, выведите любой из них.

2 3
2
2 5

2 0

1 5
9
1 2 3 4 5 6 7 8 9

0 1

Примечание

В первом примере возможны следующие варианты:

A = 2, B = 3; отступ — 0; наступил на две покрашенные

A = 2, B = 3; отступ — 1; наступил на две покрашенные

A = 2, B = 3; отступ — 2; не наступил на покрашенные

Во втором примере отступать не нужно:

A = 1, B = 5; отступ — 0; наступил на одну покрашенную

IDE

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