问题本质

从 $a$ 走到 $b$，每次走 $1$ 或 $2$ 步，不能经过 $c$ 的倍数，求最短路。

核心思路

关键观察

• 问题等价于在数轴上从 $a$ 到 $b$ 的最短路，避开 $c$ 的倍数
• 如果没有禁止点，最短路 = $\lceil \frac{b-a}{2} \rceil$（尽量用 $+2$）

算法步骤

1. 检查直接路径

计算不使用绕路的最少步数：

• 尽量多用 $Y$ 信号（$+2$）
• 剩余部分用 $X$ 信号（$+1$）

2. 检测危险点

检查区间 $[a, b]$ 内是否存在 $c$ 的倍数：

• 如果不存在，直接输出 $\lceil \frac{b-a}{2} \rceil$
• 如果存在，需要绕路

3. 绕路策略

对于每个危险点 $k \cdot c$：

• 方案1：提前避开（在 $k \cdot c - 1$ 处用 $+1$ 代替 $+2$）
• 方案2：延迟避开（在 $k \cdot c - 2$ 处用 $+2$ 代替 $+1$）
• 选择增加步数最少的方案

特殊情况

• $c = 2$：只能走奇数路径，需要特殊处理
• 多个危险点：每个危险点可能增加 $1$ 步绕路代价

复杂度

• 时间复杂度：$O(1)$（数学计算）
• 空间复杂度：$O(1)$

实现公式

def min_signals(a, b, c):
    base_steps = (b - a + 1) // 2  # 尽量用+2
    if (b - a) % 2 == 1:
        base_steps += 1
    
    # 检查是否需要绕路
    first_danger = ((a // c) + 1) * c
    if first_danger < b:
        # 需要绕路，增加1步
        base_steps += 1
    
    return base_steps