На плоскости расположены два полных бинарных дерева глубины N. Их 2x2^N листьев расположены на двух параллельных прямых и пронумерованы слева направо. Листья с одинаковыми номерами в первом и втором деревьях находятся один напротив другого. Между листьями деревьев задано соответствие – каждый из листьев одного дерева имеет ровно один соответствующий ему лист во втором дереве, и наоборот. На рисунке такие соответствия заданы прямыми отрезками между листьями. Такую конструкцию – два дерева вместе с соответствиями между листьями – называют танглеграмом. Танглеграмы, например, используются биологами при исследовании взаимосвязей генов разных видов растений.

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

Напишите программу, которая по информации о соответствии между листьями двух деревьев определит наименьшее возможное количество пересечений отрезков в графическом представлении танглеграма, которое может быть достигнуто путем выполнения операций обмена смежных поддеревьев первого дерева. Если в одной точке пересекаются больше двух отрезков, то под количеством пересечений нужно понимать количество попарных пересечений отрезков. Например, на первом рисунке соответствия 4-8, 5-5 и 6-4 образуют три пересечения.

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

1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

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

Торговец владеет тремя видами товаров: алмазы, яблоки и шелк. Для каждого товара известна стоимость в золотых монетах за единицу веса и его количество у торговца.

В стране, где живет торговец, есть N городов, которые пронумерованы от 1 до N. Родной город торговца имеет номер 1, а столица – номер N. Чтобы добраться до столицы, где торговец может продать товар, ему нужно проехать определенным маршрутом через другие города. Между некоторыми парами городов существуют дороги, проезд по которым стоит определенного количества золотых. В каждом городе взимается налог за провоз каждого из видов товара, заданный в процентах от стоимости провезенного через город товара. Известно, что выехав из любого города, торговец не может в него вернуться. Любые два города соединены не более чем одной дорогой.

Задача торговца получить наибольшую прибыль – разницу полученных в столице денег за проданный товар и расходов на путешествие в столицу. Он не обязан брать с собой весь свой товар. Торговец всегда имеет достаточно золотых для уплаты налогов, и не может рассчитаться товаром, который он везет в столицу. Все дороги ведут только в одном направлении.

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

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

Напишите программу, которая по координатам центров окружностей и их радиусам найдет пару пересекающихся окружностей.

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

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