Задача C5. Посейдон ≡
| Автор: | Г. Гренкин | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 1 |
Условие
На этапе автоматизации технического обслуживания прачечной создатели сервиса управления расписанием стирки "Посейдон" (poseidon.dvfu.ru) столкнулись с алгоритмической проблемой.
На рисунке изображены стиральные машины, как они расставлены в прачечной или на складе. Крестиком отмечена машина, вышедшая из строя. Считаем, что стиральных машин очень много, они образуют целочисленную решетку, и плохая машина имеет координаты (1, 1).
Сервис "Посейдон+" (для персонала) должен вывести алгоритм перемещения поломанной машинки в заданное место с координатами (N, M), на котором машинка не стоит.
Задача разработчиков системы "Посейдон+" — реализовать алгоритм, который найдет оптимальный способ такого перемещения. "Оптимальный" — значит за минимальное число элементарных операций. Элементарная операция — это перемещение любой стиральной машины на свободное место, соседнее с ней по горизонтали или вертикали.
Формат входного файла
N, M ∈ N.
Способ представления стандартный.
Формат выходного файла
x ∈ N0 — решение задачи оптимизации — минимальное количество перемещений (указания персоналу выводить не нужно).
Способ представления стандартный.
Ограничения
2 ≤ N, M ≤ 106Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|