Однажды двое суеверных поклонников информатики отправились на спиритический сеанс. Медиум усадила их за стол, на котором было выгравировано полное бинарное дерево высоты 10 (высота - самый длинный путь от корня до листа; высота считается по количеству вершин, дерево высоты 1 состоит из одной вершины). Это дерево устроено так, что у каждой вершины, кроме листьев, есть ровно два потомка. На вершинах дерева были выгравированы числа по следующим правилам (см. рисунок): • В корне дерева (на уровне 0) записано число 0. • Далее вершины нумеруются по порядку. • На нечётных уровнях (уровни 1,3, …) вершины нумеруются справа налево, на чётных (уровни 2,4, …) - слева направо. На столе находился спиритический указатель в форме перевёрнутого треугольника с отверстием посередине. Его положили поверх корня дерева. Указатель можно передвигать по дереву, каждый раз переходя к одному из двух потомков текущей вершины. Таким образом, указатель на пути от корня до листа проходит ровно одну вершину на каждом уровне. Набранной спиритической энергией назовем сумму выгравированных чисел, которые посетит указатель вдоль такого пути. Медиум сообщила: дух Алана Тьюринга явится только в том случае, если получится набрать максимально возможную спиритическую энергию. Чему она равна?

Задача сводится к тому, чтобы выбрать путь от корня до листа так, чтобы сумма меток, лежащих на этом пути, была максимальной. Идём по шагам. 1) Расположение уровней и нумерация - Дерево полное бинарное высотой 10: уровни 0…9 (уровень 0 – корень, уровень 9 – листья). - В корне стоит число 0. - Нумерацию вершин на каждом уровне ведут «по порядку», но по чётности уровня направление меняется: - чётные уровни (0, 2, 4, …) – слева направо; - нечётные уровни (1, 3, 5, …) – справа налево. - Пусть на уровне k вершины имеют позиции pos_k от 1 до 2^k слева направо. Нумерация уровня k начинается с S_k = 2^k − 1. 2) Формула для метки вершины по уровню и позиции - Если уровень k чётный: метка вершины с позицией pos_k равна label(k, pos_k) = S_k + (pos_k − 1) = (2^k − 1) + pos_k − 1 = 2^k + pos_k − 2. - Если уровень k нечётный: метка вершины с позицией pos_k равна label(k, pos_k) = S_k + (2^k − pos_k) = (2^k − 1) + (2^k − pos_k) = 2^{k+1} − pos_k − 1. Для примера: - уровень 1 (k=1, нечётный): левый ребёнок имеет pos_1 = 1, метка = 2^{2} − 1 − 1 = 2. Правый ребёнок pos_1 = 2 имеет метку 1. Это согласуется с правилом. - уровень 3 (k=3, нечётный): позиция 1 даёт метку 14, и т. д. 3) Как выбрать путь с максимальной суммой Обозначим best(pos_k, k) — максимальная сумма меток на пути от вершины уровня k с позицией pos_k до листа (включая метку данной вершины). Тогда для k < 9: best(pos_k, k) = label(k, pos_k) + max( best(pos_right, k+1), // переход к левому потомку: pos_right = 2 pos_k − 1 best(pos_left, k+1) // переход к правому потомку: pos_left = 2 pos_k ) а для k = 9 (лист): best(pos_9, 9) = label(9, pos_9). Заметим важную тенденцию: если рассмотреть нижние уровни, лучшее продолжение из одной вершины к листу оказывается у того потомка, который ведёт к более крупной сумме в глубине. При этом можно проверить на предпоследнем и последнем уровнях: - на уровне 8 (k=8, чётный) левая ветвь даёт большую сумму, чем правая, независимо от pos_8. - аналогично на уровне 7 (k=7, нечётный) тоже левая ветвь оказывается предпочтительной. По индукции можно показать, что best(pos_k, k) является неснижающейся функцией от pos_k (или строго убывающей по pos_k в нашем случае), т. е. меньшая pos_{k+1} даёт не меньшую (часто большую) сумму ниже. А для наших ветвей pos_{k+1} левая ветвь имеет pos_{k+1} = 2 pos_k − 1, которая меньше right-ветви pos_{k+1} = 2 pos_k. Следовательно, слева идти можно всегда и это даёт максимально возможную сумму. Итак, максимальная энергия достигается тем путём, который идёт по всем левым потомкам от корня до листа (то есть по левому краю дерева). 4) Энергия, если идти по левому краю на каждом уровне Путь слева ⟶ левый ребёнок на каждом шаге даёт pos_k = 1 для всех уровней k. Тогда метка вершины на уровне k по формуле выше для pos_k = 1: - если k чётный: label(k, 1) = 2^k − 1 - если k нечётный: label(k, 1) = 2^{k+1} − 2 Сумма по уровням k = 0…9 даём следующую последовательность: - k = 0 (чётный): 2^0 − 1 = 0 - k = 1 (нечётный): 2^2 − 2 = 2 - k = 2 (чётный): 2^2 − 1 = 3 - k = 3 (нечётный): 2^4 − 2 = 14 - k = 4 (чётный): 2^4 − 1 = 15 - k = 5 (нечётный): 2^6 − 2 = 62 - k = 6 (чётный): 2^6 − 1 = 63 - k = 7 (нечётный): 2^8 − 2 = 254 - k = 8 (чётный): 2^8 − 1 = 255 - k = 9 (нечётный): 2^{10} − 2 = 1022 Сумма этих значений: 0 + 2 + 3 + 14 + 15 + 62 + 63 + 254 + 255 + 1022 = 1690. 5) Ответ Максимальная возможная спиритическая энергия, которую сможет набрать указатель, равна 1690. Кратко: достигается путём перехода по левому ребёнку на каждом уровне (левый край дерева). Энергия равна 1690.