Задача №112589. Министерство
Однажды в далекой-далекой стране правительство создало Министерство по сокращению бумажной волокиты. Как вы наверное догадались, это было крупнейшее министерство за всю историю страны. Количество сотрудников было поистине огромным. Несмотря на это, структура министерства была очень простой: каждый сотрудник имел не более трёх подчинённых, каждый из которых снова имел не более трех подчиненных и так далее...
В результате последних выборов был избран новый министр. Он был молод, умён и непорочен, и сразу же решил оправдать название своего учреждения. Он заметил, что многие части иерархической структуры совпадают, и решил, что должны совпадать и их обязанности. А если две структуры делают одно и тоже, одна из них является лишней, и ее работники должны быть уволены. Ваша задача найти количество различных департаментов и вывести результат в необходимом формате.
Вам дана структура министерства. Каждый работник имеет одного начальника и не более трёх подчинённых(возможно ноль). Единственным исключением является министр — у него нет начальника(но так же не более трех подчинённых). Конечно нет определённого порядка, в котором перечисляются подчинённые. Департамент состоит из должностного лица, всех его подчинённых и их подчинённых, и т.д.
Есть два особых случая:
-
Департамент, в котором должностное лицо — сам министр, тогда этот департамент есть всё министерство.
- Департамент, в котором у должностного лица нет ни одного подчинённого.
Высотой департамента назовем длину максимальной последовательность сотрудников x 1 , ..., x d такую, что сотрудник x i является начальником сотрудника x i + 1 для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .
Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x A из департамента A сотрудника x B из департамента B , таким образом, что сотрудник x A является начальником сотрудником y A , тогда и только тогда, когда x B является начальником y B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.
На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .
Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n 1 , ..., n d , где d это высота всего министерства, а n i — количество различных департаментов высоты i .
Входной файл содержит единственную строку, которая описывает иерархическую структуру министерства, используя следующую нотацию. Каждый департамент кодируются строкой "( x 1 ... x k )", где k — количество подчинённых у начальника департамента, а строки x i — коды им подчиняющихся департаментов. Департамент, состоящий из одного человека, кодируется строкой "()". Структура министерства задается кодом всего министерства. Количество сотрудников министерства не превосходит 1 000 000 (включая министра).
Выходной файл должен содержать d строк, где d это высота министерства. i -ая строка должна содержать количество различных департаментов высоты i .
Приведенная картинка иллюстрирует пример из условия.
(((())())((()())(()()()))(()(())))
1 3 2 1