Кузнечик 2D

В левом-нижнем углу прямоугольной клетчатой доски размером n × m стоит k-кузнечик. За один ход k-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на k клеток.

Возможные ходы k-кузнечика для k = 3.

Необходимо передвинуть k-кузнечика в правый верхний угол доски в клетку (n, m). За какое минимальное число ходов можно передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m)?

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

В первой строке входного файла INPUT.TXT заданы три целых числа n, m и k – размеры сторон доски и максимальное число клеток, на которое может ходить k-кузнечик, соответственно (1 ≤ n, m, ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите одно число – минимальное число ходов, необходимое, чтобы передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m).

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]