В каждой клетке прямоугольной таблицы \(N\times M\) записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол.
Вводятся два числа \(N\) и \(M\) — размеры таблицы (\(1\le N\le20\), \(1\le M\le20\)). Затем идет \(N\) строк по \(M\) чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.
| Ввод | Вывод |
|---|---|
5 5 1 1 1 1 1 3 100 100 100 100 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 |
11 |
Рассмотрим разновидность двоичного дерева, которую мы назовем логическим деревом. В этом дереве каждый уровень полностью заполнен, за исключением, возможно, последнего (самого глубокого) уровня. При этом все вершины последнего уровня находятся максимально слева. Дополнительно, каждая вершина дерева имеет ноль или двоих детей.
Каждая вершина дерева имеет связанное с ней логическое значение (1 или 0). Кроме этого, каждая \(внутренняя\) вершина имеет связанную с ней логическую операцию („И“ или „ИЛИ“). Значение вершины с операцией „И“ — это логическое „И“ значений её детей. Аналогично, значение вершины с операцией „ИЛИ“ — это логическое „ИЛИ“ значений её детей. Значения всех листьев задаются во входном файле, поэтому значения всех вершин дерева могут быть найдены.
Наибольший интерес для нас представляет корень дерева. Мы хотим, чтобы он имел заданное логическое значение \(v\), которое может отличаться от текущего. К счастью, мы можем изменять логические операции некоторых внутренних вершин (заменить „И“ на „ИЛИ“ и наоборот).
Дано описание логического дерева и набор вершин, операции в которых могут быть изменены. Найдите наименьшее количество вершин, которые следует изменить, чтобы корень дерева принял заданное значение \(v\). Если это невозможно, то выведите строку «IMPOSSIBLE» (без кавычек).
В первой строке входного файла находятся два числа \(n\) и \(v\) (\(1 \le n \le 10\,000, 0 \le v \le 1\)) — количество вершин в дереве и требуемое значение в корне соответственно. Поскольку все вершины имеют ноль или двоих детей, то \(n\) нечётно. Следующие \(n\) строк описывают вершины дерева. Вершины нумеруются от \(1\) до \(n\).
Первые \((n-1)/2\) строк описывают внутренние вершины. Каждая из них содержит два числа — \(g\) и \(c\), которые принимают значение либо \(0\), либо \(1\). Если \(g=1\), то вершина представляет логическую операцию „И“, иначе она представляет логическую операцию „ИЛИ“. Если \(c=1\), то операция в вершине может быть изменена, иначе нет. Внутренняя вершина с номером \(i\) имеет детей \(2i\) и \(2i+1\).
Следующие \((n+1)/2\) строк описывают листья. Каждая строка содержит одно число \(0\) или \(1\) — значение листа.
В выходной файл выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
9 1 1 0 1 1 1 1 0 0 1 0 1 0 1 |
1 |
5 0 1 1 0 0 1 1 0 |
IMPOSSIBLE |
Дано дерево на \(n\) вершинах. На каждом ребре написан его вес. Требуется для каждого \(v\) посчитать сумму взвешенных длин всех путей в данном дереве, исходящих из \(v\). Пути \(\langle v, u \rangle\) и \(\langle u, v \rangle\) считаются различными.
Первая строка каждого теста содержит натуральное число \(n\) — количество вершин в дереве (\\(1 \leq n \leq 100\,000\\)). Следующие \(n - 1\) строк содержат по \(3\) натуральных числа \(v, u, w\) и описывают ребро дерева, соединяющее две вершины \(v\) и \(u\) и имеющее вес \(w\) (\\(1 \leq v, u \leq n\\), \\(0 \leq w \leq 10^6\\)).
Выведите \(n\) чисел — требуемое в условии.
| Ввод | Вывод |
|---|---|
3 1 2 1 1 3 3 |
4 5 7 |
Сегодня Игорь получил долгожданное разрешение на проведение эксперимента по изучению протекания химических реакций в магнитном поле. При этом используются две установки – генератор магнитного поля и манипулятор, соединяющий реагенты.
Эксперимент разбит на некоторое количество этапов, при этом некоторые из них могут быть выполнены только после завершения определенного набора других этапов. Правда известно, что хотя бы один способ проведения эксперимента существует. На каждом этапе Игорь должен управлять ровно одной из двух установок – либо генератором, либо манипулятором.
Игорь очень дорожит своим временем, и поэтому он хочет провести эксперимент, совершив наименьшее количество перемещений между пультами управления установками. Помогите ему узнать, в каком порядке следует выполнять этапы, чтобы этого добиться.
В первой строке вводится целое число \(n\) – количество этапов эксперимента \((1 \le n \le 100)\)
Следующие \(n\) строк содержат описание этапов. Пронумеруем этапы от 1 до \(n\) в некотором произвольном порядке. Тогда \(i\)-я из этих строк описывает \(i\)-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число \(r\)i – количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов – \(r\)i различных целых чисел в диапазоне от 1 до \(i\) - 1.
В первой строке выведите минимальное количество перемещений, которые придется совершить Игорю. Во второй строке выведите перестановку чисел от 1 до \(n\) – последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.
| Ввод | Вывод |
|---|---|
3 1 0 0 0 1 2 1 2 |
1 2 1 3 |
3 0 0 1 1 1 1 0 |
1 1 2 3 |
Дано подвешенное дерево, состоящее из \(N\) вершин. Вершина с номером \(1\) является корнем дерева. Каждой вершине \(i\) сопоставлено целое число \(a_i\).
Для каждой вершины \(v\) дерева рассмотрим последовательность значений в вершинах на простом пути от корня до \(v\). Требуется для каждой вершины дерева найти длину наибольшей возрастающей подпоследовательности в этой последовательности.
В первой строке входных данных находится число \(N\) — количество вершин в дереве \((1 \leq N \leq 100000)\).
Во второй строке находятся \(N\) целых чисел \(a_1, a_2, \dots, a_N\) — значения в соответствующих вершинах \((1 \leq a_i \leq 10^9)\).
В последующих \(N-1\) строках заданы ребра дерева. Каждое ребро описывается парой натуральных чисел \(u_i\) и \(v_i\) — номерами соединяемых вершин. Гарантируется, что заданная структура является деревом.
Выведите \(N\) целых чисел, разделенных пробелами. \(i\)-е число должно быть равно длине наибольшей возрастающей подпоследовательности на пути от корня до вершины \(i\).
| Ввод | Вывод |
|---|---|
5 5 3 8 6 2 1 2 1 3 2 4 3 5 |
1 1 2 2 2 |
В тридесятом государстве есть \(N\) деревень. Некоторые пары деревень соединены дорогами. В целях экономии, «лишних» дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое \(минимальное\) число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из\(P\) деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа \(изолирована\) от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.
Первая строка входного файла содержит два числа: \(N\) и \(P\) (1≤\(P\)≤\(N\)≤150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до \(N\)), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.
В выходной файл выведите единственное число – искомое количество дорог.
| Ввод | Вывод |
|---|---|
11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11 |
2 |