Информатика

Неизбежные печати

Дан неориентированный граф из N залов и M двусторонних коридоров. У каждого коридора есть положительный вес.

Для запроса s, t коридор считается неизбежным, если он встречается в любом маршруте из s в t. Маршрут может повторно посещать вершины и рёбра. При s=t разрешён пустой маршрут.

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

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

В первой строке N, M, Q (1 <= N,Q <= 100000, 0 <= M <= 200000). Далее M строк: u v w — концы коридора и его вес (1 <= w <= 10^9). Между двумя залами не более одного коридора. Затем Q строк с парами s t.

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

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

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

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

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

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

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

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

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

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

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

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

На научной смене Алекс может посетить 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. Окончание первого совпадает с началом второго; можно посетить оба.

Алекс выбирает мастер-классы научного фестиваля. Мастер-класс 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. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.

Алекс готовит приборы к экспедиции. Для включения одного прибора нужны ровно два аккумулятора с суммарным зарядом не меньше 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 останется.

Напишите программу подсчёта количества элементов последовательности натуральных чисел, запись которых в восьмеричной системе счисления четырёхзначна и оканчивается на цифру 5. В ответе запишите количество искомых элементов.

Программа получает на вход натуральные числа. Количество введённых чисел неизвестно, но не превышает 1000. Последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).

Программа должна напечатать только одно число – количество искомых элементов последовательности.

Пример работы программы

Входные данные	Выходные данные
485 557 893 3029 4125 0	3

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [10⁸; 10⁹], которые соответствуют маске ?*61*49 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [5·10⁸; 10⁹], которые соответствуют маске ?*88*81 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [3·10⁸; 6·10⁸], которые соответствуют маске ?*26*89 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [10⁸; 2·10⁸], которые соответствуют маске ?*29*61 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

закрасить клетку (i,j) в черный цвет.
для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

Входные данные
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 10⁵), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Color i j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

Выходные данные
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.

Примеры

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

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3]  является попоследовательностью массива [1,2,3] , но [3,1]  не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2]  является подотрезком массива [1,2,3] , а [1,3]  не является. Несложно заметить, что у массива длины n ровно  \( {n(n+1) \over 2}\)  подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

• У массива [1]  есть ровно один подотрезок и он является возрастающим.
• У массива [2]  есть ровно один подотрезок и он является возрастающим.
• У массива [3]  есть ровно один подотрезок и он является возрастающим.
• У массива [1,2]  есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
• У массива [1,3]  есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
• У массива [3,2]  есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3]  и [2] ) являются возрастающими.
• У массива [1,3,2]  есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12

Обелиски

На карте обсерватория находится в точке (0, 0). Даны N обелисков с целочисленными координатами, отличными от (0,0).

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

Найдите количество подходящих троек. Порядок выбора не важен.

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

В первой строке N (3 <= N <= 2000). В следующих N строках координаты x y, где -10^9 <= x,y <= 10^9. Все точки различны и не равны (0,0).

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

Выведите количество подходящих троек.

Ретрансляторы

Есть цепочка из N ретрансляторов. Радиограмма проходит их строго по порядку. Каждый ретранслятор ежедневно начинает передачу в своё фиксированное время HH:MM; длительность передачи T минут.

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

Доставка завершена в момент окончания последней передачи. Сутки длятся 1440 минут и нумеруются с 0.

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

В первой строке N и K (1 <= N <= 100000, 0 <= K <= 1440). Во второй строке начальное время HH:MM в нулевые сутки. Далее N строк: ежедневное время запуска HH:MM и длительность T (1 <= T <= 10^6).

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

Выведите номер суток D и время HH:MM, когда закончится последняя передача.

Камни

Под разрушенной башней археологи обнаружили ряд камней. На каждом высечено положительное целое число. Можно выбрать несколько пар соседних в исходном ряду камней. Для пары со значениями a и b восстанавливается a*b фрагментов.

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

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

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

В первой строке N (1 <= N <= 100000). Во второй строке N целых чисел от 1 до 10^6.

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

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

Маяк 5. Последний опасный замер

Экспедиция «МАЯК». Перед стартом исследовательского модуля тепловые замеры отсортировали от самой высокой температуры к самой низкой. Одинаковые показания встречаются несколько раз. Тревога включается только при значении строго выше x, а ровно x уже не считается перегревом. Оператор ищет последнюю запись в опасной части отсортированного журнала.

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

Первая строка содержит n и x — количество измерений и порог тревоги. Во второй строке записаны n температур по невозрастанию (от больших к меньшим).

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

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

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не возрастают (совпадения разрешены). При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 4. До закрытия шлюза

Экспедиция «МАЯК». Шлюз исследовательской базы закроется в момент x. Компьютер хранит время событий в отсортированном журнале; события с одинаковым временем возможны. Инженеру нужен номер самого позднего события, которое произошло именно до закрытия. Событие с отметкой ровно x уже не подходит.

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

В первой строке находятся n и x — количество записей и момент закрытия. Во второй строке — n временных отметок по неубыванию.

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

Выведите индекс последнего события, произошедшего строго раньше x. Если ни одно событие не успело, выведите -1.

Ограничения

1 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены).

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 3. Подбор аккумулятора

Экспедиция «МАЯК». Для дальнего выхода роботу требуется запас энергии не меньше x. Батареи на складе стоят в порядке неубывания ёмкости, некоторые имеют одинаковую ёмкость. Снабженец хочет взять первую подходящую батарею: так он не потратит более ёмкий запас без необходимости.

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

В первой строке записаны n и x — число батарей и минимально необходимая ёмкость. Во второй строке — n ёмкостей по неубыванию.

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

Выведите индекс первой батареи, ёмкости которой хватит для выхода. Если такой батареи нет, выведите -1.

Ограничения

0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены). При n = 0 вторая строка пустая.

Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.