Информатика

Скажем, что последовательность строк 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

Маяк 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) после чтения входных данных; полный перебор при поиске не используйте.

Маяк 2. Граница безопасной зоны

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

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

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

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

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

Ограничения

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

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

Маяк 1. Пропавшая радиограмма

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

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

В первой строке записаны целые числа n и x — количество радиограмм и код запроса. Во второй строке — n различных кодов, расположенных в строго возрастающем порядке.

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

Выведите номер ячейки с кодом x (нумерация с 0). Если радиограммы нет, выведите -1.

Ограничения

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

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

Алекс настраивает связь между исследовательскими станциями. Есть 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. Связь существует, но сообщение должно пройти два канала, а разрешён только один.

Алекс тестирует навигацию в музее. План музея — прямоугольная таблица из 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. Стена полностью перекрывает путь.