---> 18 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано дерево зависимостей частей эксперимента (т.е. какие действия необходимо выполнить до данного). Также для каждого действия определено, на какой установке (всего 2) оно делается. Требуется определить порядок действия, чтобы минимизировать количество переходов между установками.

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

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

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

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

В первой строке вводится целое число n – количество этапов эксперимента ( 1$ le$n$ le$100).

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

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

В первой строке  выведите минимальное количество перемещений, которые придется совершить Игорю. Во второй строке выведите перестановку чисел от 1 до n – последовательность, в которой следует выполнять этапы. Если решений несколько, выведите любое.

Примеры
Входные данные
3
1 0
0 0
1 2 1 2
Выходные данные
1
2 1 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано дерево. Каждый узел может покрасить в красный или черный цвет так, чтобы не было двух соединенных красных вершин и количество красных вершин на пути от корня до листьев было одинаковым. По заданному дереву требуется определить количество корректных способов раскраски дерева.

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

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

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

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

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

 

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

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

 

includegraphics{pics/rbtrees.1}  

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

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

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

В первой строке вводится число n – количество вершин в дереве ( 1$ le$n$ le$1000).

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

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

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

includegraphics{pics/rbtrees.1}  
Примеры
Входные данные
6
6 0
1 5
0 0
0 0
3 4
0 0
Выходные данные
3
Входные данные
4
2 0
3 0
4 0
0 0
Выходные данные
0
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Взаимной удаленностью двух вершин невзвешенного графа называется кратчайшее расстояние между ними. Необходимо построить граф, в котором сумма взаимных удаленностей вершин равна задана числу.

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
2
Выходные данные
0 0
Входные данные
8
Выходные данные
4 4
1 2
1 3
1 4
3 4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Вершины графа находятся в точках пересечения линий сетки, а горизонтальные или вертикальные ребра единичной длины существуют только между ближайшими вершинами. Необходимо пройти по каждому ребру как минимум один раз совершив как можно меньше переходов.

Недавно Билл устроился на работу полицейским. Теперь ему предстоит каждый вечер обходить свой участок, который представляет собой прямоугольник, состоящий из N×M кварталов. Каждый квартал имеет вид квадрата размером 100×100 метров, кварталы отделены друг от друга прямыми улицами.

Таким образом, через участок Билла проходит $N$ + 1 улица, идущая с запада на восток и $M$ + 1 улица, идущая с севера на юг. Перекрестки разбивают улицы на ($N$ + 1)$M$ + ($M$ + 1)$N$ отрезков, каждый из которых имеет длину 100 метров.

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

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

Вводятся целые числа N и M, разделенные пробелом (1$ \le$N, M$ \le$10 000).

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

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

Пояснение ко второму примеру

Один из возможных оптимальных путей для Билла во втором примере показан на рисунке.

Примеры
Входные данные
1 1
Выходные данные
4
Входные данные
2 2
Выходные данные
16
Входные данные
3 4
Выходные данные
38

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

В Байтленде имеется 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.

Примеры
Входные данные
4 2
1 0 1
1 1 10
10 2 5
1 2 3
Выходные данные
4

Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест