Вася работает подмастерьем в известной студии. Недавно ему поручили помогать молодому, но подающему большие надежды художественному декоратору заборов и изгородей Витезславу Смолокурову. Миссия эта очень ответственная, и от ее выполнения зависит Васино будущее.

Стиль Смолокурова очень необычен, а его работы пользуются большим спросом. Процесс работы разделен на два этапа. На первом этапе Вася делает заготовку — длинный забор, который состоит из набора цветных вертикальных планок. На втором этапе Витезслав приступает к работе.

Для того, чтобы придать забору более спокойный и гармоничный вид, он несколько раз производит следующую операцию: выбирает некоторый цвет и отрезок, после чего перекрашивает этот отрезок забора в выбранный цвет. По своей творческой натуре, Смолокуров может в корне менять концепцию узора по нескольку раз за час, поэтому иногда он перекрашивает одну и ту же планку несколько раз. Кроме того, Витезслав не хочет, чтобы какой-то узор повторялся слишком часто. Для того, чтобы избежать этого, он иногда проверяет, не совпадает ли один отрезок забора с другим.

Несложно догадаться, что и перекрашивание, и проверки осуществляет Вася. Работа эта не самая простая, поэтому Вася просит ему помочь хотя бы с проверками на совпадение.

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

После тысячелетнего правления большей частью Млечного Пути начался окончательный распад КОсмического ОБъединения ОЛигархов на несколько независимых монархий. КОБОЛ является высокоорганизованной империей, которая имеет форму огромного прямоугольного параллепипида n * m * k парсеков. Империя КОБОЛ сильно засекречена, поэтому лишь немногие знают точные значения n, m и k. Для облегчения контроля империя разделена на nmk маленьких владений по одному кубическому парсеку каждое. Эти владения занумерованы следующим образом:

В плоской стране все было как в настоящей, только плоское, и люди и горы и все, все, все. Жили в этой стране люди хорошие, но иногда попадались преступники и тогда их отвозили на плоский остров и там оставляли поразмыслить о жизни. А чтобы они не сбежали с острова, было решено построить наблюдательную вышку, с которой можно было бы следить за преступниками. Но, так как жители страны были плоскими, то и мозги у них были тоже плоскими и никак они не могли определить, в каком месте построить вышку и какой высоты. Помогите им. Вам предлагается найти самую низкую точку — координаты верхней точки вышки (плоские люди были экономными), из которой видно крайние точки острова, и найти высоту вышки. Как выяснили плоские ученые, профиль острова позволял построить вышку высотой не более 20000 метров. Профиль острова — это ломаная, имеющая примерно такой же вид как на рисунке. На острове нет лагун и с каждой вершины видны оба склона этой вершины. Точки С и Д — это крайние точки острова.

Новый Мытищинский театр «Фэст» украшен гигантской гирляндой, управляемой компьютером, в которой используются тысячи лампочек. Каждый ряд лампочек в гирлянде управляется набором переключателей, которые контролируются с использованием специальной компьютерной программы. К сожалению, электрики установили неверный набор переключателей, а сегодня вечером состоится открытие театра. Ваша задача — написать программу, которая бы заставила переключатели работать корректно. Ряд лампочек в гирлянде состоит из 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 соответственно.