|
Неисправный марсоход
(Время: 1 сек. Память: 16 Мб Сложность: 25%)
Марсоход, осуществляющий международную миссию на Марсе, неисправен. Для восстановления
его работоспособности необходимо повысить мощность его батареи.
Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до
значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные
сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал
типа Y увеличивает текущую мощность батареи на 2.
Организаторы миссии хотели бы изменить мощность батареи до необходимой, передав минимальное количество сигналов. К сожалению, из-за особенности устройства марсохода, если мощность батареи оказывается кратна целому числу c, он окончательно выходит из строя и перестаёт
реагировать на сигналы.
Требуется написать программу, которая по заданным начальной мощности батареи a, необходимой мощности батареи b и целому числу c определяет минимальное количество сигналов, которое
необходимо передать на марсоход, чтобы восстановить его работоспособность.
Входные данные
Входной файл INPUT.TXT содержит три целых числа: a, b и c, по одному на строке (1 ⩽ a < b ⩽ 109, 2 ⩽ c ⩽ 109, a не кратно c, b не кратно c).
Выходные данные
В выходной файл OUTPUT.TXT требуется вывести одно целое число: минимальное количество сигналов, которые необходимо
передать на марсоход.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
7
3 | 3 |
| 2 | 4
10
3 | 4 |
Пояснения к примерам
В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y,
X, Y. Мощность батареи меняется следующим образом: 2 → 4 → 5 → 7.
Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X,
Y, X, Y. Мощность батареи меняется следующим образом: 4 → 5 → 7 → 8 → 10.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
