Подразделы

Другие разделы

Дата и время

19/12/2024 20:20:28

Авторизация

Задачи Интернет-соревнования для подготовки школьников к областной олимпиаде

A. Пропавшая буква B. Палиндромизация C. Логи чата D. Сортировка имен E. Уравнение F. Яблоки на бинарном дереве G. Замощение прямоугольника H. Сдача I. Треугольные суммы J. Игра в дележ

F. Яблоки на бинарном дереве

Ограничения: время – 250ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Строго бинарное дерево – это дерево, каждая ветка которого либо является конечной веткой, либо разветвляется на два поддерева. На каждой конечной ветке этого дерева растут 1 или более яблок. При этом дерево является сбалансированным – если какая-то ветка делится на два поддерева, то на каждом поддереве растет одинаковое количество яблок. Структуру дерева будем описывать с помощью квадратных скобок, каждая пара соответствует разветвлению дерева на два поддерева. Внутри "[]" описывается структура поддеревьев, если они не являются конечными ветками. Примеры описаний:

В первой строке содержится структура дерева. Длина строки не превышает 150 символов. Вложенность скобок не превышает 25.

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

Пример ввода 1

[]

Пример вывода 1

Пример ввода 2

[[][[]]]