UniLecs #182. Комбайн

Задача: комбайну необходимо собрать урожай с прямоугольного поля размера N*M метров. Ширина комбайна - 1 метр. Комбайну нужно собрать урожай со всего поля. Он начинает движение с верхнего левого угла в горизонтальном направлении до конца поля, затем он поворачивает направо и далее движется аналогичным образом. Так он продолжает свое движение по спирали до тех пор, пока весь урожай с поля не будет собран.

Определите количество поворотов комбайна, которые необходимо совершить в процессе работы?

Входные данные: N, M - натуральные числа от 1 до 10^9.

Вывод: количество поворотов

Пример:

1. N = 3; M = 4;

Answer = 4

2. N = 5; M = 3;

Answer = 5

Идея: задачу можно решить несколькими способами, рассмотрим 2:

1. Сведение задачи к задаче меньшей размерности

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

Поле NxM. Собираем урожай с первого ряда, увеличиваем счетчик на единицу. Далее меняем размерность задачи на Mx(N-1), т.е. условно мы "поварачиваем" наше поле, отсчет также начинается с верхнего левого угла, но размер поля стал Mx(N-1).

Повторяем этот процесс, пока кол-во рядов не станет равно 1.

2. Поиск закономерности

Можно заметить некоторую закономерность в кол-ве поворотов в каждом ряду в зависимости от размерности поля.

Случай 1. M >= N. Кол-во столбцов больше рядов. 

В этом случае, только в 1м и последнем обрабатываемом ряду (средний ряд) кол-во поворотов будет равно 1, во всех остальных рядах комбайн будет совершать поворот ровно 2 раза. Смотрим рисунок, одним цветом показаны повороты в одном ряду. 

Тогда: если M >= N, то кол-во поворотов равно 2*(N - 2) + 2 = 2 * (N - 1)

Случай 2. M < N. Кол-во столбцов меньше рядов.

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

Тогда: если M < N, то кол-во поворотов равно 2*(M - 1) + 1 = 2*M - 1

Вторым способом мы свели решение задачи к одно формуле, ответ которой находится за константное время.

Реализация:

https://gist.github.com/unilecs/d71c345a1b1939f1d794ae058757c357

Play-test: https://dotnetfiddle.net/WXHlJg