Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

3.2. Алекс и датчики на тропе#100093

На прямой исследовательской тропе есть n подходящих мест для установки датчиков. Координаты всех мест известны и различны. Алекс должен поставить ровно k датчиков, не более одного в каждом месте.

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

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

Первая строка содержит целые числа n и k (2 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n различных целых координат xᵢ (0 ≤ xᵢ ≤ 10⁹) в произвольном порядке.

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

Выведите максимальное минимальное расстояние.

Пояснения к примерам

Пример 1. Можно поставить датчики в точках 1, 4 и 8. Минимальное расстояние равно 3.

Пример 2. Нужно занять оба места.

—Войти и решать

2.4. Алекс и сеансы в лабораториях#100090

На научной смене Алекс может посетить n лабораторных сеансов. Сеанс i начинается в момент sᵢ, заканчивается в момент fᵢ и приносит vᵢ исследовательских баллов. Баллы начисляются только за полностью посещённый сеанс.

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

Алекс может выбирать любые сеансы и пропускать остальные. Найдите максимальную сумму баллов.

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

Первая строка содержит целое число n (1 ≤ n ≤ 200 000). Следующие n строк содержат по три целых числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 10⁹, 1 ≤ vᵢ ≤ 10⁹). Сеансы перечислены в произвольном порядке; совпадения времён допускаются.

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

Выведите максимальное количество баллов, которое сможет набрать Алекс.

Пояснения к примерам

Пример 1. Подходят сеансы 1, 3 и 5: 7 + 9 + 10 = 26 баллов.

Пример 2. Окончание первого совпадает с началом второго; можно посетить оба.

Алгоритмы Бинарный поиск в массиве Динамическое программирование: один параметр Теория расписаний

—Войти и решать

1.5. Алекс и ограниченный абонемент#100086

Алекс выбирает мастер-классы научного фестиваля. Мастер-класс i идёт с момента sᵢ до момента fᵢ и приносит vᵢ баллов опыта. Чтобы получить баллы, его нужно посетить целиком.

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

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

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

Первая строка содержит целые числа n и K (1 ≤ n ≤ 50 000, 1 ≤ K ≤ min(30, n)). Следующие n строк содержат целые числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 10⁹, 1 ≤ vᵢ ≤ 10⁹). Порядок произвольный; совпадения времён допустимы.

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

Выведите максимальную сумму баллов.

Пояснения к примерам

Пример 1. Лучше посетить только шестой мастер-класс. Цепочка 1, 3, 5 дала бы 26 баллов, но требует трёх посещений.

Пример 2. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.

Алгоритмы Бинарный поиск в массиве Динамическое программирование: два параметра Теория расписаний

—Войти и решать

1.2. Алекс и парные аккумуляторы#100083

Алекс готовит приборы к экспедиции. Для включения одного прибора нужны ровно два аккумулятора с суммарным зарядом не меньше L. Аккумуляторы могут иметь разный заряд.

У Алекса n аккумуляторов. Каждый можно поставить не более чем в один прибор, разделять заряд между приборами нельзя. Приборов достаточно много. Найдите максимальное количество приборов, которые Алекс сможет включить одновременно.

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

Первая строка содержит целые числа n и L (2 ≤ n ≤ 200 000, 1 ≤ L ≤ 2·10⁹). Вторая строка содержит n целых зарядов aᵢ (1 ≤ aᵢ ≤ 10⁹).

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

Выведите максимальное количество включённых приборов.

Пояснения к примерам

Пример 1. Подходят пары зарядов (1, 9), (2, 8), (3, 7).

Пример 2. Можно использовать пары (3, 9) и (4, 8); аккумулятор с зарядом 2 останется.

"Два указателя"Алгоритмы Жадный алгоритм Использование сортировки

✓ 2✗ 0—Войти и решать

Кластеры роботов - 2#62562

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

Вы находитесь рядом с роботом номер \(n\). Роботом номер \(t\) можно управлять, если он связан с \(n\)-м некоторой цепочкой проводов, то есть

либо если \(t = n\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество роботов.

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

Формат выходных данных
Для каждого набора входных данных выведите в первой строке через пробел максимальное количество роботов, управление над которыми можно получить, и количество действий \(k\), которое для этого понадобится.

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

Деревья Жадный алгоритм Конструктив Обход в глубину

✓ 1✗ 01 000средняяВойти и решать

Кластеры роботов#62485

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

Вы находитесь рядом с роботом номер \(1\). Роботом номер \(t\) можно управлять, если он связан с первым некоторой цепочкой проводов, то есть

либо если \(t = 1\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Деревья Жадный алгоритм Конструктив Обход в глубину

✓ 1✗ 1900средняяВойти и решать

Возрастающие пути#44510

Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x², ……, вес k-го ребра делится на x^k.

Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.

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

В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.

В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

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

Выведите одно целое число k - максимальную длину возрастающего пути.

Примечание

Простым путем называется такой путь, что все вершины в нем различны.

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 8 1 3 6 1 4 3	2
2	6 1 2 2 2 3 4 3 4 2 4 5 4 5 6 8	3

Алгоритмы на графах Арифметические алгоритмы (Теория чисел)Обход в глубину Применение обхода в глубину

✓ 2✗ 31 200средняяВойти и решать

Мишины кубики#43718

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.

Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 4 2 aaaaaa bbbb	aabaabaa

"Два указателя"Жадный алгоритм Задача на реализацию Использование сортировки Простые задачи на перебор

✓ 28✗ 1141 100средняяВойти и решать

Эльфы и олени#38920

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел a_i – строптивость оленей ( 0 ≤ a_i ≤ 10⁹). В третьей строке записаны n целых чисел b_i – темперамент эльфов ( 0 ≤ b_i ≤ 10⁹).

Выходные данные
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: d_i, e_i, 1, e_i, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры

№	Входные данные	Выходные данные
1	4 6 2 3 4 5 1 3 2 2 5 2	2 1 1 2 3 4 5

Бинарный поиск по ответу Быстрая сортировка Жадный алгоритм Эвристические методы

✓ 18✗ 571 100средняяВойти и решать

Деревни#38444

В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.

Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.

Формат выходных данных
В выходной файл выведите единственное число — искомое количество дорог.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 1 2 3 2	1
2	11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11	2	группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.

Алгоритмы на графах Динамическое программирование Динамическое программирование на графах Обход в глубину

✓ 1✗ 121 100средняяВойти и решать

Красота фейерверка#33127

В лаборатории теоретической пиротехники изучают новые технологии организации

фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном

фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят

операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и

называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина

является родителем. При этом от любой вершины можно добраться до корня,

последовательно переходя от вершины к ее родителю. Вершина, которая не является

родителем никакой другой вершины, называется листом. Если вершина x является

родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что

вершина и ее родитель соединены ребром.

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин

2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети

вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T¹ — само дерево T. Для m > 1 рассмотрим дерево T^{m – 1} . Выполним следующую операцию: для каждого листа x дерева T^{m – 1} создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T^m .

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

Рис. 2. Пример возведения дерева в степени 1, 2 и 3

Путем в дереве называется последовательность вершин, в которой две соседние

вершины соединены ребром. Все вершины в пути должны быть различны.

Для того, чтобы оценить красоту фейерверка, необходимо определить, какое

максимальное количество вершин может содержать путь в дереве, которым представляется

фейерверк. На рис. 3 приведен путь в дереве T², содержащий максимальное количество

вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Рис. 3. Путь в дереве T² , содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Формат входных данных

Первая строка входных данных содержит два натуральных числа n и m — количество

вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn —

номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).

Формат выходных данных

Требуется вывести одно целое число — красоту фейерверка, представляемого

деревом T^m.

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

Динамическое программирование Динамическое программирование Динамическое программирование на поддеревьях Обход в глубину Применение обхода в глубину

✓ 3✗ 211 100средняяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

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

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

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

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

✓ 2✗ 771 200средняяВойти и решать

3.5. Алекс и настройка радиосвязи#100096

Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.

Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.

Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.

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

Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).

Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 10⁹). Между одной парой станций не более одного канала.

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

Выведите минимальную мощность либо −1, если передать сообщение за допустимое число переходов невозможно.

Пояснения к примерам

Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.

Пример 2. Связь существует, но сообщение должно пройти два канала, а разрешён только один.

Алгоритмы Бинарный поиск по ответу Обход в ширину

—Войти и решать

3.4. Алекс и ночной музей#100095

Алекс тестирует навигацию в музее. План музея — прямоугольная таблица из n строк и m столбцов. Клетка # занята стеной, клетка . свободна. В клетке S находится Алекс, а в клетке T — пульт управления.

За один шаг можно перейти в соседнюю по стороне свободную клетку. Клетки S и T тоже свободны. Выходить за границы таблицы нельзя.

Найдите минимальное количество шагов от S до T и число различных маршрутов такой длины. Маршруты различны, если различаются последовательности посещённых клеток. Количество маршрутов выведите по модулю 1 000 000 007.

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

Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 500, 2 ≤ nm ≤ 200 000). Далее идут n строк по m символов ., #, S, T. Символы S и T встречаются ровно по одному разу и находятся в разных клетках.

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

Выведите два целых числа: длину кратчайшего маршрута и количество таких маршрутов по модулю 1 000 000 007. Если пульт недостижим, выведите -1 0.

Пояснения к примерам

Пример 1. Можно обойти стены сверху и справа либо слева и снизу. Оба маршрута содержат пять шагов.

Пример 2. Стена полностью перекрывает путь.

Алгоритмы Динамическое программирование на графах Обход в ширину

—Войти и решать

3.1. Алекс и две смены наблюдателей#100092

Алекс распределяет n наблюдателей по двум сменам: утренней и вечерней. Каждый человек должен попасть ровно в одну смену; пустая смена допускается.

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

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

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Следующие m строк содержат пары u, v (1 ≤ u, v ≤ n, u ≠ v). Каждая неупорядоченная пара встречается не более одного раза.

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

Выведите количество допустимых распределений по модулю 1 000 000 007.

Пояснения к примерам

Пример 1. У цепочки 1–2–3 два варианта смен, у наблюдателя 4 ещё два независимых варианта.

Пример 2. Трёх наблюдателей, попарно обязанных работать в разных сменах, в две смены распределить нельзя.

Алгоритмы Обход в глубину Поиск компонент связности

—Войти и решать

2.5. Алекс и запуск научного центра#100091

Алекс руководит запуском научного центра. Нужно выполнить n работ. Работа i занимает dᵢ минут и после начала выполняется без остановок.

Для некоторых пар работ указано требование: работа u должна закончиться прежде, чем начнётся работа v. Если у работы несколько предшественников, должны завершиться все. Приступить к работе можно ровно в момент завершения последнего предшественника.

Работы без предшественников можно начать в момент 0. Исполнителей и оборудования достаточно: независимые работы могут идти одновременно. Найдите минимальный момент, когда будут закончены все работы. Если требования противоречивы и выполнить все работы невозможно, выведите −1.

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000). Вторая строка содержит n целых длительностей dᵢ (1 ≤ dᵢ ≤ 10⁹). Следующие m строк содержат u, v: работа u должна завершиться перед началом v. Номера различны и лежат от 1 до n. Одинаковых упорядоченных пар нет; циклы могут встречаться.

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

Выведите минимальный момент завершения всех работ или −1.

Пояснения к примерам

Пример 1. Работы 1 и 2 начинаются одновременно. Работа 3 заканчивается в момент 9, работы 4 и 5 — в моменты 11 и 15, работа 6 — в момент 16.

Пример 2. Каждая работа в цикле ждёт завершения другой.

Алгоритмы Динамическое программирование на графах Топологическая сортировка

—Войти и решать

2.3. Алекс и стоимость восстановления сети#100089

Алекс восстанавливает сеть из n исследовательских станций. Некоторые пары уже соединены работающими двусторонними кабелями. По цепочке кабелей можно передавать сообщения через промежуточные станции.

Новый кабель можно проложить между любой парой различных станций u и v. Это стоит cᵤ + cᵥ монет. Если к станции подводят несколько новых кабелей, её стоимость оплачивается за каждый из них. Работающие кабели бесплатны и сохраняются.

Найдите минимальную общую стоимость новых кабелей, после добавления которых сообщение со станции 1 сможет дойти до любой станции.

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Вторая строка содержит n целых чисел cᵢ (1 ≤ cᵢ ≤ 10⁹).

Следующие m строк содержат номера концов работающего кабеля u и v (1 ≤ u, v ≤ n, u ≠ v). Между одной парой станций не более одного работающего кабеля.

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

Выведите минимальную общую стоимость. Если сеть уже связна, выведите 0.

Пояснения к примерам

Пример 1. Минимальные стоимости в трёх компонентах равны 2, 4 и 9. Добавим кабели 2–5 и 2–6: (2 + 4) + (2 + 9) = 17.

Пример 2. Станции уже связаны.

Алгоритмы Жадный алгоритм Поиск компонент связности

—Войти и решать

1.3. Алекс и доставка экспонатов#100084

Алекс должен перевезти n ящиков с экспонатами. На складе ящики стоят в очереди, массы ящиков равны a₁, …, aₙ.

За один рейс Алекс забирает несколько первых оставшихся ящиков. Менять порядок и пропускать ящики нельзя. Каждый ящик перевозится целиком, ровно один раз. Масса груза в одном рейсе не должна превышать грузоподъёмность машины C.

Алекс может сделать не более k рейсов. Найдите минимальную целую грузоподъёмность C, которой хватит, чтобы перевезти все ящики.

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

Первая строка содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n целых чисел aᵢ (1 ≤ aᵢ ≤ 10⁹).

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

Выведите минимальную грузоподъёмность.

Пояснения к примерам

Пример 1. Подходят рейсы [4, 2], [7], [3, 5]. При грузоподъёмности 7 понадобятся четыре рейса.

Пример 2. Единственный рейс должен вместить все ящики.

Алгоритмы Бинарный поиск по ответу Жадный алгоритм

—Войти и решать

Why Did the Cow Cross the Road III#90425

Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

Соседние коровы ещё имеют возможность войти, но только через одни ворота и с большой очередью, потому что каждой нужно ответить на длинный список вопросов, прежде чем войти.

Для каждой из \(N\) коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

Определите минимально возможное время, за которое все коровы войдут на ферму.

ФОРМАТ ВВОДА (файл cowqueue.in):

Первая строка ввода содержит \(N\), положительное целое число, не более 100. Каждая из последующих \(N\) строк описывает одну корову, задавая время прибытия и время, которое требуется ей для ответов на вопросы. Каждое из этих чисел - положительное целое число не более 1,000,000.

ФОРМАТ ВЫВОДА (файл cowqueue.out):

Определите минимально возможное время, в которое все коровы завершат обработку.

Жадный алгоритм Задачи на моделирование Использование сортировки

—Войти и решать

Angry Cows#90387

Беси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.

Имеется \(N\) стогов сена расположенных в целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\) в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги сена в диапазоне \(x-R \ldots x+R\).

Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\). Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\) коров разрушить все стоги сена на сцене.

ФОРМАТ ВВОДА (файл angry.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)) и \(K\) (\(1 \leq K \leq 10\)). Каждая из оставшихся \(N\) строк содержит целые числа \(x_1 \ldots x_N\) (каждое в интервале \(0 \ldots 1,000,000,000\)).

ФОРМАТ ВЫВОДА (файл angry.out):

Выведите минимальную энергию \(R\), с которой должна приземлиться каждая корова, для того чтобы разрушить все стоги сена.

Бинарный поиск по ответу Жадный алгоритм Задачи на моделирование

—Войти и решать