МШП: Тренировка 04.11.2010

Компания "Лампоматика" занимается производством очень больших люстр для очень больших залов. Люстра состоит из нескольких ярусов, каждый из которых состоит из кольца и прикрепленных к нему хрустальных подвесок или других уже собранных люстр.

Производством люстры занимается специальный робот. У робота есть неограниченный запас хрустальных подвесок и пустых колец, кроме того, у он может помещать уже собранные части люстры в стек, который изначально пуст. Операции робота контролируются программой из списка команд.

Когда робот получает команду "a", он берет новый кусок хрусталя и кладет его в стек-буфер. По командам "1" - "9" робот берет соответствующее число собранных "подлюстр" из стека, прикрепляет их к новому кольцу и помещает результат в стек. В конце работы на вершине стека остается только один элемент - собранная люстра.

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

Люстры считаются одинаковыми если каждое кольцо содержит те же элементы в том же относительном порядке на кольце. Например, если робот получает команду "4", то если элементы в стеке в порядке \(\langle i_1, i_2, i_3, i_4\rangle\) (\(i_1\) на вершине стека), то та же самая люстра будет получена когда в стеке \(\langle i_2, i_3, i_4, i_1\rangle\), \(\langle i_3, i_4, i_1, i_2\rangle\) или \(\langle i_4, i_1, i_2, i_3\rangle\).