ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Пьяный король 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Как-то на шахматной доске m × n с нечётными длинами сторон собрались вместе король, конь и слон. Завели разговор про обходы шахматной доски. И оказалось, что всем троим вечно не везёт в этом вопросе. Слон пожаловался, что вообще не может обойти доску, побывав на каждой клетке ровно один раз, поскольку ему разрешено ходить только по клеткам одного цвета. Конь сказал, что он умеет обходить все клетки доски, но не умеет делать это так, чтобы в конце пути вернуться в ту клетку, с которой он начал обход. А король, хоть и умел обходить доску, уже много лет безуспешно пытался найти замкутый обход длины mn.
С горя трое друзей выпили, после чего продолжили беседу. Король сказал, что на днях нашёл замкнутый обход длины mn − 1 + sqrt(2). Конь и слон стали над королём смеяться: «Да ты же сейчас пьян, ты её вообще не обойдёшь!» Король действительно был настолько пьян, что не мог сделать подряд два хода в одном направлении. Но тем не менее король у них на глазах обошёл доску да ещё заявил, что этот обход — кратчайший (с учётом его нетрезвого состояния).
Теперь, чтобы проверить, что король их не обманул, слону с конём нужно знать длину кратчайшего обхода пьяного короля. Но сами они вычислить эту длину не могут — они ведь тоже пьяные! Вы же проходили мимо и, к несчастью, оказались трезвыми, поэтому и решать эту задачу придётся Вам.
Помните, что обход доски должен удовлетворять следующим условиям:
  • Король должен начать и закончить обход в углу доски.
  • Каждая клетка, кроме первой, должна быть посещена ровно один раз.
  • Король не может сделать подряд два хода в одном направлении.
  • Запрещается пересекать свой путь, иначе король запутается и пойдёт не в ту сторону.

Исходные данные

Единственная строка содержит два целых числа: m и n (6 < m, n < 500; m и n — нечётные).

Результат

Выведите длину кратчайшего обхода пьяного короля c точностью 10−9. Гарантируется, что такой обход всегда существует.

Пример

исходные данныерезультат
7 7
55.213203435596425732025330863145

Замечания

Пример одного из кратчайших обходов шахматной доски 7 × 7, удовлетворяющих условию задачи:
Problem illustration
Автор задачи: Игорь Чевдарь
Источник задачи: XIII Открытый командный чемпионат УрГУ по программированию
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1631. Пьяный король 2