Задача 5. Неисправный марсоход ≡

Условие

Марсоход, осуществляющий международную миссию на Марсе, неисправен. Для восстановления его работоспособности необходимо повысить мощность его батареи.

Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал типа Y увеличивает текущую мощность батареи на 2.

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

Требуется написать программу, которая по заданным начальной мощности батареи a, необходимой мощности батареи b и целому числу c определяет минимальное количество сигналов, которое необходимо передать на марсоход, чтобы восстановить его работоспособность.

Формат входных данных

Входные данные содержит три целых числа: a, b и c, по одному на строке.

Формат выходных данных

Требуется вывести одно целое число: минимальное количество сигналов, которые необходимо передать на марсоход.

Ограничения

1 ≤ a < b ≤ 10⁹, 2 ≤ c ≤ 10⁹, a не кратно c, b не кратно c

Описание подзадач и системы оценивания

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

Пояснения к примерам

В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y, X, Y. Мощность батареи меняется следующим образом: 2 ↦ 4 ↦ 5 ↦ 7.

Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X, Y, X, Y. Мощность батареи меняется следующим образом: 4 ↦ 5 ↦ 7 ↦ 8 ↦ 10.

Примеры тестов

2
7
3

3

4
10
3

4

Разбор

Для решения подзадачи 1 можно использовать полный перебор вариантов очередного сигнала. Время работы полного перебора составляет O(2^b − a) и не превышает 2¹⁵.

Для решения подзадачи 2 можно использовать динамическое программирование. Обозначим как dp[i] минимальное число сигналов, необходимое, чтобы мощность батареи марсохода составляла i. Тогда dp[i] = min(dp[i − 1], dp[i − 2]) + 1, если i не кратно c и dp[i] =  + ∞, если i кратно c. Время работы этого решения O(b − a).

Для подзадачи 3, где c = 2 оптимальна следующая последовательность: необходимо (b − a) / 2 раз отправить на марсоход сигнал Y, поскольку b и a оба нечетны, все промежуточные значения будут нечетными.

Перейдем теперь к полному решению.

Рассмотрим два соседних значения, кратных c и числа между ними: ck, ck + 1, ck + 2, …, c(k + 1). Заметим, что, поскольку значение мощности равное ck запрещено, первое из этих значений, которое примет мощность батареи, равно ck + 1. Будем далее отправлять на марсоход сигналы Y, пока мощность не примет одно из двух значений: ck + k − 2 или ck + k − 1. В первом случае далее следует подать сигнал X, чтобы мощность приняла значение ck + k − 1. Теперь, подав сигнал Y, мы переводим мощность в следующий отрезок чисел между кратными c.

Итого для преодоления такого отрезка требуется ⌊ (c + 1) / 2⌋ сигналов (здесь ⌊ x⌋ означает x, округленное вниз).

Осталось разобраться с начальным отрезком от a до первого числа, кратного c и с заключительным отрезком от последнего числа кратного c до b. Это можно сделать аналогично. Наконец, следует не забыть о случае, когда между a и b совсем нет чисел, кратных c, в этом случае ответ равен ⌊ (b − a) / 2⌋.