Динамическое программирование

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

• Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.

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

Ограничения: длина исходной последовательности от 1 до 100.

Входные данные
В первой строке находится последовательность символов от A до Z.

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

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.

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

Примеры

№	Входные данные	Выходные данные
1	([(]	()[()]
2	(	()

Назовем подпоследовательностью массива 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

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

Алекс выбирает приборы для экспедиции. У него есть n разных приборов. Каждый существует в единственном экземпляре и имеет массу wᵢ и научную ценность vᵢ. Массы и ценности выбранных приборов складываются.

В рюкзак помещается груз общей массой не более W. Алекс хочет получить максимальную суммарную ценность. Среди всех наборов с такой ценностью он выбирает набор наименьшей общей массы. Можно не брать ни одного прибора.

Найдите максимальную ценность и соответствующую минимальную массу.

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

Первая строка содержит целые числа n и W (1 ≤ n ≤ 200, 1 ≤ W ≤ 10 000). Следующие n строк содержат wᵢ и vᵢ (1 ≤ wᵢ ≤ 20 000, 1 ≤ vᵢ ≤ 10⁹).

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

Выведите два целых числа: максимальную ценность и минимальную массу набора с этой ценностью.

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

Пример 1. Нужно взять третий и четвёртый приборы: ценность 6 + 12 = 18, масса 2 + 5 = 7.

Пример 2. Ценность обоих одиночных наборов равна 5, поэтому выбираем более лёгкий.

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

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

Алекс готовит оборудование экспедиции к испытаниям, которые продлятся n часов. В каждый час всё оборудование нужно обеспечить электричеством. В час i питание от основной сети стоит aᵢ монет, а питание от резервного генератора — bᵢ монет.

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

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

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

Первая строка содержит целые числа n и C (1 ≤ n ≤ 200 000, 0 ≤ C ≤ 10¹⁴).

Вторая строка содержит n целых чисел a₁, …, aₙ — стоимость основной сети по часам. Третья строка содержит n целых чисел b₁, …, bₙ — стоимость работы генератора по часам. Для всех i: 0 ≤ aᵢ, bᵢ ≤ 10⁹.

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

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

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

Пример 1. Выгодно включить генератор на часы со 2-го по 6-й. Эти часы стоят 2 + 7 + 2 + 7 + 2 = 20 монет. Ещё 5 монет стоит запуск, а в 1-й и 7-й часы сеть стоит по 2 монеты. Всего 29. В 3-й и 5-й часы генератор дороже сети, но включить его несколькими отдельными периодами нельзя.

Пример 2. Генератор дешевле в каждом часу, но за все три часа экономит только 3 монеты. Запуск за 10 монет не окупается; лучше пользоваться сетью.

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 2^𝑛 навыков, пронумерованных 1 до 𝑑. Эти навыки расположены на листьях полного двоичного дерева высоты 𝑛, изначально все навыки имеют уровень 1. Пример такого дерева для 𝑛 = 3 приведен на иллюстрации ниже.



После этого вы начинаете прокачивать навыки следующим образом.
• Навыки прокачиваются посредством заполнения двоичного дерева снизу вверх.
• Для очередной вершины дерева вы должны выбрать и записать в нее один из двух навыков, записанных в
непосредственных детях этой вершины (на рисунке из детей в родителя ведут стрелки).
• Уровнем навыка считается число вершин, в которых выбран этот навык.
Пример корректного распределения навыков по дереву для 𝑛 = 3 приведен ниже.


В этом примере первый навык имеет уровень 4, седьмой – уровень 3, четвертый и пятый – уровень 2, а второй, третий, шестой и восьмой не были прокачаны ни разу, поэтому остались на уровне 1.
Кроме прокачки персонажа, в игре есть 𝑚 различных квестов, с помощью которых можно получать монетки. Квесты активируются после того, как все дерево навыков было заполнено.
Квесты бывают трех типов:
1. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго меньше 𝑘𝑖 .
2. «𝑒𝑥𝑎𝑐𝑡 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется равен 𝑘𝑖 .
3. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго больше 𝑘𝑖 .
Так как монеты – очень ценный ресурс в игре «Бинарная Сила», вы хотите узнать максимальное количество монет, которое возможно получить с помощью имеющихся квестов после улучшения всех навыков.

Формат входных данных
Каждый тест состоит из нескольких независимых наборов входных данных. Первая строка содержит одно целое число 𝑡 – количество наборов входных данных (1 ≤ 𝑡 ≤ 10⁴). Далее следует описание наборов входных данных.
Каждый набор начинается со строки, содержащей два целых числа 𝑛 и 𝑚 – высоту дерева навыков и количество квестов соответственно (1 ≤ 𝑛 ≤ 15; 0 ≤ 𝑚 ≤ 50 000). Число навыков при этом равно 𝑑 = 2^𝑛.
Далее следуют 𝑚 строк, 𝑖-я из которых содержит четыре целых числа 𝑡𝑖, 𝑥𝑖, 𝑘𝑖, 𝑠𝑖 – тип квеста и его описание (1 ≤ 𝑡𝑖 ≤ 3; 1 ≤ 𝑥𝑖 ≤ 𝑑; 1 ≤ 𝑘𝑖 ≤ 𝑛; 1 ≤ 𝑠𝑖 ≤ 10⁹). Типы квестов следуют в том же порядке, в котором они перечислены в условии: 𝑡𝑖=1 соответствует квесту типа «𝑙𝑒𝑠𝑠», 𝑡𝑖 = 2 – квесту типа «𝑒𝑥𝑎𝑐𝑡» и 𝑡𝑖 = 3 – квесту типа «𝑚𝑜𝑟𝑒».
Гарантируется, что сумма 𝑑 по всем наборам входных данных не превосходит 2¹⁶ и сумма 𝑚 по всем наборам входных данных не превосходит 50 000

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