Презентація
Ви - вчений, який досліджує алгоритми на бінарних деревах. Бінарне дерево - це структура даних, яка складається з вузлів розгалуження та листків. Кожен вузел розгалуження має лівого і правого сина, кожен син - або вузол розгалуження, або лист. Коренем дерева є вузол розгалуження, у якого немає батьків.
Ви готуєтесь до презентації, де Вам потрібно створити зображення бінарних дерев за допомогою програмного забезпечення. Ви вже створили картинку, на якій зображено бінарне дерево, яке складається з одного вузла розгалуження і двох листків (Рисунок 1). Проте раптово у Вас зламалась функція, яка дозволяє програмі створювати рисунок. Ви дуже засмутились, так як через п'ять годин Вам потрібно зробити презентацію перед великою аудиторією.
Ви вирішили створити зображення бінарних дерев, використовуючи лише функції копіювання, стиснення і вставки. Тобто Ви можете здійснювати лише наступні два типи операцій:
Скопіювати поточну фігуру у буфер обміну (фігура копіюється у буфер, попередній його вміст видаляється).
Вставити скопійовану фігуру (з масштабуванням, якщо необхідно), прикріпивши корінь вставленої фігури до листка поточної (скопійовану фігуру можна вставляти багато разів).
Більше того, Ви вирішили створти фігуру, здійснивши найменшу кількість операцій вставки, оскільки саме операція вставки вимагає багато часу. Ваша задача - знайти наименшу кількість операцій вставки для створення заданої фігури.
Рисунок 1: початковий стан
Відповідь до прикладу 1 (Рисунок 4) дорівнює 3, так як потрібну фігуру можна отримати здійснивши наступний мінімум операцій.
Рисунок 2: проміжний етап 1
Рисунок 3: проміжний етап 2
Рисунок 4: Завдання
Вхідні дані
Вхідний рядок задає бінарне дерево. Граматика виразу заданється наступною БНФ:
::= | "(" ")"
::= "()"
Вхідні дані задовольняють вказаному синтаксису. Вважайте, що кожне вхідне дерево має хоча б один і не більше 10^5 вузлів розгалуження.
Вихідні дані
Вивести найменшу кількість операцій вставки, які потрібно виконати для отримання заданого бінарного дерева.