Команда пушистых спасателей сидела без дела в своём дупле, когда неожиданно поступил сигнал бедствия. В считанные мгновения все были на своих местах, и дирижабль бурундучков-спасателей отправился в путь.

Будем считать, что действие происходит на декартовой плоскости. База спасателей расположена в точке ( x ₁ , y ₁ ) , а сигнал бедствия поступил из точки ( x ₂ , y ₂ ) .

Благодаря инженерному искусству Гаечки, летательный аппарат спасателей может произвольное количество раз в любые моменты времени мгновенно изменить свою текущую скорость и направление движения. Единственное ограничение — величина скорости дирижабля относительно воздуха не может превосходить метров в секунду.

Разумеется, как настоящий спасатель, Гаечка хочет лететь так, чтобы оказаться на месте происшествия как можно быстрее. Дело осложняется тем, что в небе дует ветер, который влияет на перемещение дирижабля. Согласно прогнозу погоды, в ближайшие t секунд скорость ветра будет характеризоваться вектором ( v _x , v _y ) , а по прошествии t секунд скорость ветра станет равна ( w _x , w _y ) . Данные вектора определяют как направление ветра, так и его скорость. Формально, если дирижабль находится в точке ( x , y ) , его собственная скорость относительно воздуха равна нулю и при этом дует ветер ( u _x , u _y ) , то для любого неотрицательного вещественного числа , через секунд дирижабль окажется в точке с координатами .

Гаечка занята управлением дирижаблем, поэтому она попросила Чипа вычислить, как скоро они смогут быть на месте, с чем он легко справился. Однако Дейл убеждён, что Чип не справился вычислить ответ и назвал случайное значение, лишь бы не ударить в грязь лицом перед Гаечкой. Чтобы пристыдить Чипа, Дейл попросил вас посчитать правильный ответ.

Гарантируется, что скорость ветра в любой момент времени строго меньше максимально возможной скорости дирижабля относительно воздуха.

Гарри Поттер и Тот-Кого-Нельзя-Называть снова сошлись в смертельном поединке. На этот раз они стоят в противоположных концах коридора длины l метров и одновременно пускают в противника свои смертельные заклинания. Известно, что магический импульс заклинания Гарри распространялся со скоростью p метров в секунду, а магический импульс заклинания Сами-Знаете-Кого — со скоростью q метров в секунду.

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

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

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

Так как дороги всегда обходятся недёшево, правительства государств новообразованного союза попросили вас помочь им оценить затраты. Для этого вам была выдана карта, которая представляет собой клетчатый прямоугольник из n строк по m клеток в каждой. Любая клетка карты либо принадлежит одному из трёх государств, либо является областью, на которой можно построить дорогу, либо является областью, на которой дорогу построить нельзя. Проходимыми являются все клетки, принадлежащие государствам, а также все клетки, в которых построены дороги. Из любой проходимой клетки можно перемещаться вверх, вниз, вправо и влево, если соответствующая такому перемещению клетка существует и является проходимой.

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

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

На планете Бублик идёт война. Каждый из городов планеты принадлежит одному из нескольких враждующих государств. На планете есть n городов, расположенных вокруг дырки от Бублика и пронумерованных числами от 1 до n в порядке их обхода по кругу. Расстояние между любыми двумя соседними по кругу городами (в том числе между городом номер n и городом номер 1 ) одно и то же, а именно 42 бубликанских километра.

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

Вам дана политическая карта планеты Бублик. Требуется найти два города, принадлежащих одному государству, расстояние между которыми максимально.