Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.

«У исполнителя Калькулятор две команды:

· прибавь 3

· умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»

Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).

Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).

Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из \(N\) подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.

Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до \(N\).

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

Власти города на каждой полосе разместили видеокамеру, поэтому если Иннокентий едет по встречной полосе (при ее наличии) или, в случае одностороннего движения, в сторону противоположную предписанной знаками, то после поездки против правил по каждой из полос ему придется заплатить штраф в размере одной тысячи тугриков этой страны.

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

Иннокентий еще не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида «Какой минимальный штраф надо заплатить, чтобы добраться из пункта A в пункт B?». Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.

Так как многие из вас рано или поздно будут проходить собеседование на работу в эту фирму, продемонстрируйте, что вы тоже умеете решать эту задачу.

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

При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.

Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.

Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.

Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.

Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.

Комментарий

Верхний рисунок иллюстрирует исходное размещение игрушек в коробках, а нижние — варианты итогового расположения игрушек (оптимальный вариант слева).