ЛОШ 2013: Командная олимпиада

Новый Мытищинский театр «Фэст» украшен гигантской гирляндой, управляемой компьютером, в которой используются тысячи лампочек. Каждый ряд лампочек в гирлянде управляется набором переключателей, которые контролируются с использованием специальной компьютерной программы. К сожалению, электрики установили неверный набор переключателей, а сегодня вечером состоится открытие театра. Ваша задача — написать программу, которая бы заставила переключатели работать корректно. Ряд лампочек в гирлянде состоит из n лампочек и контролируется n переключателями. Лампочки и переключатели занумерованы слева направо от 1 до n. Каждая лампочка может быть либо включена, либо выключена. Каждый тестовый пример в этой задаче будет содержать начальную и желаемую конечную конфигурации лампочек. Исходно предполагалось, что каждый переключатель будет контролировать одну лампочку. Однако ошибка в электронике привела к тому, что каждый переключатель помимо своей лампочки также изменяет состояние двух (или одной, если основная лампочка находится c краю) соседних с ней. Так, самый левый переключатель (i = 1) изменяет состояние двух самых левых лампочек (1 и 2), а самый правый (i = n) — двух самых правых (n - 1 и n). Каждый из оставшихся переключателей (1 ≤ i ≤ n) изменяет состояние трех лампочек с номерами i - 1, i и i + 1. Исключение составляет единственный случай, когда имеется ровно одна лампочка и один переключатель. В этом случае этот переключатель контролирует эту лампочку. Таким образом, если, к примеру, лампочка 1 включена, а лампочка 2 выключена, то при нажатии на переключатель 1 лампочка 1 выключится, а лампочка 2 включится. Определим минимальную стоимость перехода из одной конфигурации к другой как минимальное количество переключателей, которое требуется нажать, чтобы получить из начальной конфигурации конечную.

Можно представить состояние ряда лампочек как двоичное число, где 0 означает, что лампочка выключена, а 1 — что лампочка включена. Так, в частности, двоичное число 01100 представляет собой ряд из пяти лампочек, среди которых вторая и третья включены, а остальные выключены. Можно превратить эту конфигурацию в конфигурацию 10000, нажав последовательно на переключатели 1, 4 и 5, но дешевле сделать это, просто изменив состояние переключателя 2. Напишите программу, которая определит, на какие переключатели следует нажать, чтобы перевести начальную конфигурацию лампочек в конченую за минимальной стоимость. В некоторых случаях подобное может оказаться невозможным. Отметим, что для компактности представления двоичные числа записываются как десятичные, то есть вместо 01100 и 10000 используются числа 12 и 16 соответственно.