Задача .
Яблоня (40 баллов)
Входной
файл: input.txt
Выходной
файл: output.txt
Время
тестирование: 3 сек/тест(примерно)
Червяк оказался
у яблони, которая растет в виде двоичного дерева (см. рис), причем известно,
что на каждой ветке растет некоторое количество яблок. Червяк хочет доползти до
верха дерева, прогрызя при этом как можно меньше яблок, и двигаясь при этом
только вверх. Требуется написать программу, которая определила бы минимальное
количество яблок, которое нужно прогрызть червяку, чтобы добраться до верха.
Яблоня имеет высоту N (0<N<=10), а каждая ветка имеет высоту 1м.
Для каждой развилки известно, сколько яблок растет на левой и правой ветке,
причем развилки пронумерованы следующим образом: корень имеет номер 1, а все
остальные развилки нумеруются по возрастанию слева направо, снизу вверх (как на
рисунке).
Входные данные:
В первой строке входного файла записано одно число – N. Далее в 2N-1 строках записана информация о ветвях:
по два числа (Li,
Ri) на
строке – количество яблок на соответствующей ветке (0<=Li, Ri<=32000).
Выходные данные:
В выходной файл
необходимо вывести одно число – минимальное количество яблок, которое должен
прогрызть червяк.
Пример входных
данных (соответствует рисунку):
2
1 3
5 5
1 2
Пример выходных
данных:
4
Новости | 