HDU 1049 Climbing Worm（簡單模擬/數學題）

HDU 1049 Climbing Worm - 蠕虫爬井模擬

這是一道極簡單的模擬題，也可以用數學公式直接計算。

題目大意

蠕虫在深 n 寸的井底。每分鐘向上爬 u 寸，然後休息 1 分鐘滑落 d 寸（d < u）。問幾分鐘能爬出井口。部分分鐘算整分鐘；剛好爬到頂端算成功。

模擬解法

int main() {
    int n, u, d;
    while (cin >> n >> u >> d, n||u||d) {
        int time = 0, height = 0;
        while (height < n) {
            height += u; time++;
            if (height >= n) break;
            height -= d; time++;
        }
        cout << time << endl;
    }
    return 0;
}

數學優化（O(1) 計算）

每 2 分鐘淨上升 u - d。最後一次爬升不滑落。

if (n <= u) ans = 1;
else {
    int cycles = (n - u + u - d - 1) / (u - d);  // 向上取整
    ans = cycles * 2 + 1;
}

樣例驗證

• 10 2 1：每 2 分鐘淨升 1。需 8 循環(16分)到達 8，第 17 分鐘爬 2 到達 10 → 17
• 20 3 1：每 2 分鐘淨升 2。需 9 循環(18分)到達 18，第 19 分鐘爬 3 到達 21 → 19

複雜度

• 模擬：O(n/(u-d)) ≤ 100，瞬間結束
• 數學：O(1)