Задача №1261. Катакомбы-1
Пиратские катакомбы на острове Сокровищ были вырыты по следующему принципу. После скрытого входа расположена пещера, из которой выходят два туннеля – налево и направо. Каждый из туннелей заканчивается пещерой, из которой так же выходит два туннеля, и т.д. Длина каждого туннеля равна единице. Конечные пещеры, которые находятся на расстоянии \(D\) от входа, не имеют дальнейших выходов. Никакие туннели между собой не пересекаются, и не ведут к одной пещере. Число \(D\) называют глубиной катакомб (более формально, пещеры образуют полное бинарное дерево глубины \(D\), его листья называются конечными пещерами)
В каждой из конечных пещер спрятан один сундук с сокровищами. Перед прибытием на остров Капитана Джека Воробья пираты решили переместить эти сундуки в соответствии с последними указаниями Капитана. Пираты нарисовали план катакомб и пронумеровали конечные пещеры слева направо. Потом для каждого сокровища был установлен номер пещеры, в которой он должен оказаться перед прибытием Капитана. После перемещения в каждой пещере снова окажется только один сундук.
Чтобы обеспечить безопасность сокровищ, пираты могут только обменивать между собой сундуки из двух пещер. Только после окончания одного обмена можно начинать другой. Необходимо найти наименьшее суммарное расстояние, которое пиратам необходимо будет нести сундуки, чтобы разместить их требуемым образом.
Тесты в этой задаче являются открытыми. Вам задано несколько входных файлов, каждый из них рассматривается как отдельная задача с соответствующим номером, в систему необходимо отправить ответ на тест. Тесты расположены здесь.
По предоставленным входным файлам, которые содержат описание пещеры с сокровищами, создайте соответствующие выходные файлы, которые содержат минимальное суммарное расстояние, которое пиратам придется нести сундуки, и последовательность обменов. Выходные файлы нужно сдавать в задачи с соответствующим номером.
Первая строка содержит одно целое число \(D\) – глубину катакомб. Вторая строка содержит \(2^D\) разных целых чисел от \(1\) до \(2^D\), \(i\)-ое из них идентифицирует номер пещеры, в которую должен попасть сундук, находившийся сначала в пещере \(i\).
Первая строка файла должна содержать единственное целое число – минимальное суммарное расстояние, которое пройдут пираты с сокровищами. Вторая строка: целое число \(K\) – соответствующее количество обменов. Каждая последующая из \(K\) строк должна содержать два числа, которые обозначают номера пещер, между которыми производится обмен. Обмены должны быть указаны в том порядке, в котором они должны производиться.
2
4 3 1 2
20
3
3 4
1 4
3 2