Задача №115412. Кузнечик 2D
В левом-нижнем углу прямоугольной клетчатой доски размером \(n\times m\) стоит \(k\)-кузнечик. За один ход \(k\)-кузнечик перемещается по доске вправо, вверх или вправо-вверх по диагонали не более чем на \(k\) клеток.
Возможные ходы \(k\)-кузнечика для \(k = 3\).
Необходимо передвинуть \(k\)-кузнечика в правый верхний угол доски в клетку \((n, m)\). За какое минимальное число ходов можно передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\)?
В первой строке заданы три целых числа \(n\), \(m\) и \(k\) — размеры сторон доски и максимальное число клеток, на которое может ходить \(k\)-кузнечик, соответственно (\(1 \le n, m, k \le 10^9\)).
Выведите одно число — минимальное число ходов, необходимое, чтобы передвинуть \(k\)-кузнечика из клетки \((1, 1)\) в клетку \((n, m)\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | \(n, m \le 10\), \(k = 1\) | первая ошибка | |
| 2 | 16 | \(n, m, k \le 10\) | 1 | первая ошибка |
| 3 | 17 | \(n, m \le 10^9\), \(k = 1\) | 1 | первая ошибка |
| 4 | 18 | Гарантируется, что ответ равен 1 или 2 | первая ошибка | |
| 5 | 34 | нет | 1–4 | первая ошибка |
9 8 5
3
2 2 1
1