Дистанционный практикум по программированию

Внутри пирамиды Хеопса есть N комнат, в которых установлены 2M модулей, составляющих M устройств. Каждое устройство состоит из двух модулей, которые располагаются в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за 0.5 условных единиц времени. В начальный момент времени модули всех устройств переходят в подготовительный режим. Для каждого модуля имеется некоторый целочисленный период времени, в течение которого тот находится в подготовительном режиме. По истечении этого времени модуль мгновенно включается, после чего опять переходит в подготовительный режим. Устройством можно воспользоваться только в тот момент, когда одновременно включаются оба его модуля. Индиана Джонс сумел проникнуть в гробницу фараона. Обследовав ее, он включил устройства и собрался уходить, но в этот момент проснулся хранитель гробницы. Теперь Джонсу необходимо как можно быстрее попасть в комнату с номером N, в которой находится выход из пирамиды. При этом из комнаты в комнату он может попадать только при помощи устройств, так как проснувшийся хранитель закрыл все двери в комнатах пирамиды. Необходимо написать программу, которая получает на входе описание расположения устройств и их характеристик, а выдает значение оптимального времени и последовательность устройств, которыми надо воспользоваться, чтобы попасть из комнаты номер 1 в комнату номер N за это время.