2025年 北马其顿编程竞赛 (Macedonian programming contests 2025)

赛事等级： 社区与地区级竞赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：奇迹世界 (Светот на Чудата)

题目描述

克里斯（Chris）生活在奇迹世界中，这个世界可以被表示为一个坐标系。他的家位于坐标原点 $(0, 0)$，而他女朋友的家位于坐标 $(W, H)$。

克里斯有两种移动方式：

1. 使用超能力：克里斯可以在一个步骤内向右移动 $C$ 个单位，向上移动 $R$ 个单位。换句话说，如果他当前位于 $(X, Y)$，使用一次超能力后他将到达 $(X + C, Y + R)$。
2. 步行：他可以在一个步骤内向任何方向（左、右、上、下）移动 $1$ 个单位。即从 $(X, Y)$ 移动到 $(X+1, Y)$、$(X-1, Y)$、$(X, Y+1)$ 或 $(X, Y-1)$。

克里斯必须到达他女朋友的家。由于他非常懒惰，他希望尽可能减少步行的步数（使步行的总移动距离最小化）。

给定女朋友家的坐标 $(W, H)$ 以及超能力的参数 $C$ 和 $R$，请计算克里斯到达目的地所需的最少步行步数。

输入格式

• 第一行包含 4 个整数，用空格分隔：$W, H, C, R$ ($1 \le W, H, C, R \le 10^{15}$)。其中 $(W, H)$ 是目的地的位置，$C$ 和 $R$ 是超能力的参数。

评分说明：

• 30% 的分数满足：$W = H$，$C = R$，且 $1 \le W, H \le 1,000,000$。
• 另有 30% 的分数满足：$1 \le W, H \le 1,000,000$。
• 其余分数满足最大数据范围限制。

输出格式

• 输出一个整数，代表克里斯所需的最少步行步数。

限制条件

• 时间限制： 100 毫秒
• 内存限制： 64 MB

样例说明

样例 1： 输入：10 10 3 3 输出：2 解释：克里斯使用 3 次超能力到达 (9, 9)，然后步行 2 步到达 (10, 10)；或者使用 4 次超能力到达 (12, 12)，然后步行 4 步回到 (10, 10)。显然 2 步更少。

样例 2： 输入：11 11 3 3 输出：2 解释：克里斯连续使用 4 次超能力：$(0, 0) \to (3, 3) \to (6, 6) \to (9, 9) \to (12, 12)$。从 $(12, 12)$ 出发，他向左走一步，向下走一步到达 $(11, 11)$，总共步行 2 步。

解题思路分析

1. 数学模型： 假设克里斯使用了 $k$ 次超能力，那么他通过超能力到达的位置是 $(k \cdot C, k \cdot R)$。 从该位置到达目的地 $(W, H)$ 需要步行的步数为：

   $$\text{Steps}(k) = |W - k \cdot C| + |H - k \cdot R|$$

   我们的目标是找到一个非负整数 $k$，使得 $\text{Steps}(k)$ 最小。

2. 函数性质： 函数 $f(k) = |W - kC| + |H - kR|$ 是一个关于 $k$ 的凸函数（具体来说是多个绝对值函数之和）。对于这类函数，我们可以使用三分搜索 (Ternary Search) 来寻找最小值，或者通过分析极值点来解决。

3. 极值点分析： 最小值通常出现在 $k \approx W/C$ 或 $k \approx H/R$ 附近。 由于 $W, H$ 高达 $10^{15}$，我们不能遍历 $k$。我们需要检查以下几个 $k$ 的取值：

   • $k_1 = \lfloor W/C \rfloor$ 和 $k_2 = \lceil W/C \rceil$
   • $k_3 = \lfloor H/R \rfloor$ 和 $k_4 = \lceil H/R \rceil$
   • 特殊情况：$k=0$。

   计算这几个可能的 $k$ 对应的 $\text{Steps}(k)$，取最小值即可。

版权信息

• 项目： Macedonian Programming Contests 2025
• 赛事： Community and Regional competition
• 版权方： ZIM (北马其顿计算机科学家协会)