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