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

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 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

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

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

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

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

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

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

Входные данные
В первой строке входного файла содержится целое число n (3≤n≤100000) - число комнат в норе Бильбо.

В следующих n−1 строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от 1 до n.

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

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

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

Примечание
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.

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

В Байтленде имеется n лесозаготовительных поселков, каждый из которых расположен вблизи какой-либо реки. В настоящее время в Байттауне находится большая пилорама, которая обрабатывает все деревья, срубленные в Королевстве. Деревья сплавляются вниз по рекам от поселков, где они срублены, к пилораме в Байттауне. Король Байтленда решил поставить k дополнительных пилорам в поселках, чтобы уменьшить стоимость сплава деревьев. После установки пилорам деревья не обязательно должны сплавляться в Байттаун, а могут быть обработаны на ближайшей пилораме, находящейся ниже по течению рек. Очевидно, что деревья, срубленные в окрестности поселка с пилорамой, вообще не сплавляются по рекам.

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

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

Задание
Напишите программу, которая:
<> * читает из стандартного ввода количество поселков, количество дополнительных пилорам, которые будут установлены, количество срубленных в каждом поселке деревьев и описание рек,
*вычисляет минимальную стоимость сплава деревьев после установки дополнительных пилорам,
*выводит результат в стандартный вывод.

Входные данные
Первая строка входных данных содержит два целых числа: n — количество поселков, не считая Байттауна (2 ≤ n ≤ 100), и k
 — количество дополнительных пилорам, которые будут установлены (1 ≤ k ≤ 50 и k ≤ n). Поселки нумеруются числами 1 , 2 ,...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

w_i — количество деревьев, срубаемых в поселке i за год (0 ≤ w_i ≤ 10 000),
v_i — ближайший поселок (либо Байттаун) вниз по реке от поселка i (0 ≤ v_i ≤ n),
d_i — расстояние (в километрах) по реке от поселка i до поселка v_i (1 ≤ d_i ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные
Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения


Рисунок сверху иллюстрирует входные данные примера. Номера поселков указаны внутри кругов. Числа под кругами обозначают количество деревьев, срубаемых вблизи данного поселка. Числа над стрелками указывают длины рек.

Пилорамы должны быть установлены в поселках 2 и 3.

Сверхсекретный завод, расположенный высоко в горах, занимается изготовлением новейших систем контроля торсионных полей – нанокристаллов. Нанокристалл состоит из нескольких атомов, некоторые из которых попарно связаны сверхпрочными торсионными связями.

Нанокристалл стабилен, если между любыми двумя его атомами можно построить соединяющую их цепочку связей, возможно с использованием других атомов. Например, из четырех атомов A, B, C и D, в котором между собой связаны пары A - B, A - C, B - C и B - D, стабилен. Если же, например, в нанокристалле из данных четырех атомов связаны только пары A - B и C - D, то кристалл нестабилен, поскольку, например, A и C не соединены никакой цепочкой связей.

Для любой пары атомов стабильного нанокристалла определена их взаимная удаленность – минимальная длина цепочки из связей, которая их соединяет. Например, рассмотрим описанный выше нанокристалл. Взаимная удаленность атомов A и B равна единице (они соединены напрямую), а взаимная удаленность C и D равна двум (они соединены цепочками C - B - D и C - A - B - D, длина кратчайшей цепочки равна двум).

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

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

Входные данные
На вход программы поступает число c (1<c<10 000).

Выходные данные
В первой строке  выведите два целых числа n и m – количество атомов и связей в разработанном нанокристалле, соответственно. Будем считать, что атомы нанокристалла пронумерованы от 1 до n. Следующие m строк должны содержать по два целых числа – пары атомов, которые следует соединить торсионными связями. Если решений несколько, выведите любое.

Если искомого нанокристалла не существует, выведите в первой и единственной строке  выходных данных два нуля.

Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

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

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

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

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель — черный;

2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

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

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин в дереве (\(1 \le n \le 1000\)).

Пусть вершины дерева пронумерованы числами от \(1\) до \(n\). Следующие \(n\) строк содержат по два числа — для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел действительно задает двоичное дерево.

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

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.

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

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

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

Формат входных данных
На первой строке записано целое число \(n\) — количество этапов эксперимента (\(1 \le n \le 100\)).

Следующие \(n\) строк содержат описание этапов. Пронумеруем этапы от 1 до \(n\) в некотором произвольном порядке. Тогда \(i\)-я из этих строк описывает \(i\)-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число \(r_i\) — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — \(r_i\) различных целых чисел в диапазоне от 1 до \(i - 1\).

Формат выходных данных
На первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. На второй строке выведите перестановку чисел от 1 до \(n\) — последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 10⁹+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N² всех тестов не превысит 2⋅10⁴.


Входные данные: 
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

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

Выходные данные: 
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 8 0 SS....RR 00100000 00100000 00011000 00000100 00000100 00000011 00000000 00000000 13 0 SSS.RRRSS.RR. 0001000000000 0001000000000 0001000000000 0000111000000 0000000000000 0000000000000 0000000000000 0000000001000 0000000001000 0000000000110 0000000000000 0000000000000 0000000000000	4 12	Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8. Имеется четыре схемы маршрутизации: 1→3→4→6→7,2→3→5→6→8 1→3→5→6→7,2→3→4→6→8 1→3→4→6→8,2→3→5→6→7 1→3→5→6→8,2→3→4→6→7 Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12. Одна из возможных схем маршрутизации: 1→4→5 2→4→7 3→4→6 8→10→12 9→10→11 В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
2	2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000	3 1	Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4. имеется три схемы маршрутизации: 1→3→1→5, 2→3→4 1→3→4, 2→3→1→5 1→5, 2→3→1→3→4 Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3. Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3	5 3 2 RS. 010 101 100 4 2 .R.S 0100 0010 1000 0100 4 2 .SR. 0000 0011 0100 0010 5 2 .SSRR 01000 10101 01010 00000 00000 6 2 SS..RR 001010 000010 000010 000010 100101 000000	2 1 2 6 24