#P11697. [ROIR 2025] 二维蚱蜢

[ROIR 2025] 二维蚱蜢

题目背景

翻译自 ROIR 2025 D1T1

题目描述

在一个大小为 n×mn \times m 的矩形网格的左下角位置有一只蚱蜢。每次蚱蜢可以向右、向上或者向右上方对角线方向跳跃,且每次跳跃的距离最多为 kk 个格子。

对于 k=3k = 3 的情况,蚱蜢的可移动方向如下所示:

问:最少需要多少次跳跃,才能使蚱蜢从左下角的格子 (1,1)(1, 1) 移动到右上角的格子 (n,m)(n, m)

输入格式

第一行包含三个整数 nn, mm, 和 kk,分别表示网格的行数、列数和蚱蜢每次最多能跳跃的格子数(1n,m,k1091 \leq n, m, k \leq 10^9)。

输出格式

输出一个整数,表示将蚱蜢从格子 (1,1)(1, 1) 移动到格子 (n,m)(n, m) 所需的最少跳跃次数。

9 8 5
3
2 2 1
1

提示

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 1515 n,m10n, m \leq 10k=1k = 1
22 1616 n,m,k10n, m, k \leq 10
33 1717 n,m109n, m \leq 10^9k=1k = 1
44 1818 保证答案为 1122
55 3434