Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
733. Яблоки на бинарном дереве
Комбинаторика, теория ПойаОлимпиадные задачи на русском языке
| 25/12/2007 | Интернет-соревнование для подготовки школьников к областной олимпиаде (F) |
Ограничения: время – 250ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Строго бинарное дерево – это дерево, каждая ветка которого либо является конечной веткой,
либо разветвляется на два поддерева.
На каждой конечной ветке этого дерева растут 1 или более яблок.
При этом дерево является сбалансированным – если какая-то ветка делится на два поддерева,
то на каждом поддереве растет одинаковое количество яблок.
Структуру дерева будем описывать с помощью квадратных скобок, каждая пара соответствует разветвлению дерева на два поддерева.
Внутри "[]" описывается структура поддеревьев, если они не являются конечными ветками. Примеры описаний:
В первой строке содержится структура дерева. Длина строки не превышает 150 символов. Вложенность скобок не превышает 25.
Вывести минимальное число яблок, при котором на каждой конечной ветке дерева с заданной структурой растет не менее одного яблока и оно является сбалансированным.
Пример ввода 1
[]
Пример вывода 1
2
Пример ввода 2
[[][[]]]
Пример вывода 2
8
