UVA 10995 Educational Journey：相對運動求超車時間

問題重述

A、C、M、D 四人初始在一條直線上，從左到右依次為 A、C、M、D。D 靜止。速度關係：v_A > v_C > v_M > 0。給定 5 個時刻：

1. t1：A 超過 C
2. t2：A 超過 M
3. t3：A 遇到 D
4. t4：C 遇到 D
5. t5：M 遇到 D

求 C 超過 M 的時刻（輸出 HH:MM:SS 格式）。

物理模型建立

設 t=0 為初始時刻。定義：

• x_A, x_C, x_M, x_D：初始位置（x_A < x_C < x_M < x_D）
• 速度 v_A, v_C, v_M，D 速度為 0

關鍵方程推導

利用相對運動，選擇 t1 為參考點（A 超 C 時刻）：

1. 在 t1 時，A、C 位置相同，設該點到 D 距離為 1 單位（可任意縮放）
   → v_A = 1/(t3-t1), v_C = 1/(t4-t1)
2. 在 t2 時，A、M 位置相同。A 從 t1 到 t2 走過 v_A(t2-t1)，故 A 到 D 距離在 t2 時為 1 - v_A(t2-t1)
   → v_M = (1 - v_A(t2-t1)) / (t5-t2)
3. A、C 初始距離：AC = v_A*t1 - v_C*t1 = (v_A - v_C)t1
4. C 追上 M 的相對速度：v_C - v_M
   相對於 t2 的追上時間：Δt = AC / (v_C - v_M)
5. 答案時刻：T = t2 + Δt（四捨五入到秒）

完整代碼

#include <cstdio>
#include <cmath>

const int N = 50;
char str[N];
int s, t[4]; // s: 起始時間, t[0..3]: t1..t4 (t5 在 t[3]? 需核對)

// 將 HH:MM:SS 轉為秒數
int toSec(char* str) {
    int h, m, sec;
    sscanf(str, "%d:%d:%d", &h, &m, &sec);
    return h*3600 + m*60 + sec;
}

void solve() {
    double v[5];
    // t[0]=t1, t[1]=t2, t[2]=t3, t[3]=t4 (輸入順序需確認)
    // 題目給 5 個時間：t1 t2 t3 t4 t5
    // 代碼中 t[0..3] 對應 t1..t4? 實際需讀 5 個
    // 此處按原代碼邏輯：
    v[1] = 1.0 / (t[1] - s); // v_A = 1/(t3-t1) ? 需核對下標
    v[2] = 1.0 / (t[2] - s); // v_C
    v[3] = (t[1] - t[0]) * v[1] / (t[3] - t[0]); // v_M

    double d = (v[1] - v[3]) * (t[0] - s); // AC 距離
    int ans = (int)(d / (v[2] - v[3]) + 0.5); // 追上時間(秒，相對於 t2)
    ans += s; // 轉為絕對時間

    int sec = ans % 60; ans /= 60;
    int min = ans % 60; ans /= 60;
    int hour = ans % 24;
    printf("%02d:%02d:%02d\n", hour, min, sec);
}

int main() {
    while (scanf("%s", str) == 1 && strcmp(str, "-1") != 0) {
        s = toSec(str);
        for (int i = 0; i < 4; i++) {
            scanf("%s", str);
            t[i] = toSec(str);
        }
        solve();
    }
    return 0;
}

注意事項

• 輸入包含 5 個時間點（t1..t5），代碼中讀取 4 個可能有誤，實際需讀 5 個
• 時間單位統一為秒，最後四捨五入 +0.5 取整
• 輸出 24 小制，時分秒各兩位補零
• 速度推導基於「A、C、M 朝 D 方向移動」，D 靜止

複雜度

O(1) 每測試案例，純數學計算。