Если в предыдущей задаче нам удалось использовать рекурсивное решение, то здесь придется обходиться итеративным. Как обычно, будем искать число опасных стопок для произвольного N. Сложность в том, что стопки сами по себе разные. Разобьем их на 4 класса:
Тип 1 - опасные, содержат три или более контейнера A подряд.Теперь перейдем к стопкам размером N + 1. Каждая стопка из рассмотренных ранее классов породит 2 стопки, причем несложные логические рассуждения (возьмите карандаш) показывают, что:
из стопки 1-го класса получится 2 стопки 1-го класса;Теперь о граничных (вообще-то, для итеративных схем лучше говорить "о начальных") условиях. Их можно написать как для N = 1 (по одной стопке типа 3 и 4), так и для N = 0 (одна стопка типа 4 - собственно, стопок нет вообще). Заметим, что как и в предыдущей задаче, нам достаточно знать количества стопок высоты на единицу меньшей текущей. После этого решение становится совсем простым.