Хорошо известно, что самым живучим биологическим видом на Земле являются тараканы. Они живут всюду, где можно найти еду. А поскольку в еде они неприхотливы, то живут они просто везде.
Маленький Леша учится в школе на космической станции. Во время одного из школьных состязаний его класс вышел в финал. Задание финального конкурса заключается в том, чтобы как можно быстрее выморить всех тараканов в грузовом модуле.
За долгую историю проведения состязаний у школьных команд выработалась единая тактика в этом конкурсе. Тактика такова: в один из отсеков модуля запускается ядовитый газ, после этого открывается одна перегородка, соединяющая этот отсек с одним из соседних. Тараканы, не выдерживая запаха газа, перебегают в соседнее помещение. После того, как в обработанном отсеке не останется ни одного таракана, перегородка закрывается. Далее аналогичным образом обрабатывается другой отсек и т.д. Главная цель – загнать всех тараканов в шлюзовой отсек грузового модуля. Тогда открывается внешняя дверь и, со свистом и визгом, тараканов засасывает в открытый космос.
В своём классе Леша как раз отвечает за программирование пульта управления перегородками. Перегородки открываются довольно медленно, поэтому для победы в конкурсе важно обойтись минимально возможным количеством подъемов перегородок. Ваша задача состоит в том, чтобы помочь Леше подсчитать такое минимальное количество.
Выходные данные
Выведите минимальное количество перегородок, которые надо открыть (а потом закрыть), чтобы перегнать всех тараканов в шлюзовый отсек.
