Задача "1. Кузнечик 2D" Контеста "Региональный этап ВСОШ 2025 9-11 задачи"
Максимальное количество баллов за задачу: 69
Временной лимит: 1 с
Ограничение памяти: 512 МБ
Условие
В левом-нижнем углу квадратной клетчатой доски размером n × m стоит k-кузнечик. За один ход k-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на k клеток. Необходимо передвинуть k-кузнечика в правый верхний угол доски в клетку (n, m). Выведите, за какое минимальное число ходов можно передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m). Формат входных данных: В первой строке заданы три целых числа n, m и k — размеры сторон доски и максимальное число клеток, на которое может ходить k-кузнечик, соответственно (1 <= n, m, k <= 10^9). Формат выходных данных: Выведите одно число — минимальное число ходов, необходимое, чтобы передвинуть k-кузнечика из клетки (1, 1) в клетку (n, m).

Тесты
Тест 1:
Входные данные:
9 8 5
Выходные данные:
3
Тест 2:
Входные данные:
2 2 1
Выходные данные:
1