UVA 1529 Clock：時鐘指針重疊次數計算

題目大意

給定起始時間 sh:sm 和結束時間 eh:em（12 小制），計算在這段時間區間內（含端點），時針與分針重疊的次數。

重疊時刻規律

時針與分針每 12/11 小時重疊一次，即約每 65.4545... 分鐘。在 12 小時（720 分鐘）內重疊 11 次（不含 0:00 重疊兩次）。

將時間縮放 100 倍為整數單位：

• 12 小時 = 12 × 60 × 100 = 72000 單位
• 重疊間隔 = 72000 / 11 = 6545 單位（向下取整）

計算公式

將時間 h:m 轉為縮放單位 t = (h×60 + m) × 100。
區間 [s, e] 內的重疊次數 = ⌊e / 6545⌋ - ⌈(s-100) / 6545⌉ + 1，簡化為：

count = e/D - (s-100)/D   // 整數除法，D=6545

完整代碼

#include <cstdio>

const int T = 12 * 60 * 100; // 72000
const int D = 6545;          // 72000/11 取整

int solve(int s, int e) {
    if (e < s) e += T; // 跨 12 小時
    return e / D - (s - 100) / D;
}

int main() {
    int sh, sm, eh, em;
    printf("Program 3 by team X\n");
    printf("Initial time Final time Passes\n");
    while (scanf("%d%d%d%d", &sh, &sm, &eh, &em) == 4) {
        int s = (sh * 60 + sm) * 100;
        int e = (eh * 60 + em) * 100;
        printf(" %02d:%02d %02d:%02d%8d\n", sh, sm, eh, em, solve(s, e));
    }
    printf("End of program 3 by team X\n");
    return 0;
}

關鍵細節

1. 時間縮放：×100 避免浮點誤差，所有計算在整數域
2. 跨午夜處理：e < s 時加 T
3. 端點包含：(s-100)/D 確保起始時刻若恰好重疊被計入
4. 輸出格式：完全匹配題目要求的表頭與結尾

複雜度

O(1) 每查詢，極快。

數學驗證

12 小時內重疊時刻（分鐘）：
0, 65.45, 130.91, 196.36, 261.82, 327.27, 392.73, 458.18, 523.64, 589.09, 654.55
間隔 ≈ 65.4545 分鐘 = 6545.45 縮放單位，取 6545 整數除法近似，實測 AC。