e-olymp
Змагання

2018 Всероссийская олимпиада школьников по информатике, Москва

Неисправный марсоход

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

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

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

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

Входные данные

Три целых числа a, b и c, по одному на строке (1a < b109, 2c109, a не кратно c, b не кратно c).

Выходные данные

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

Пояснение

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
2
7
3
Вихідні дані #1
3
Вхідні дані #2
4
10
3
Вихідні дані #2
4
Джерело 2018 Всероссийская олимпиада школьников по информатике, Региональный этап, день 2, Москва, 28 января 2019, Задача А