等紅綠燈 (APCS 2025-01 初級) 題解

Editorial for 等紅綠燈 (APCS 2025-01 初級)

簡潔題意

紅綠燈以「綠燈 \(a\) 秒、紅燈 \(b\) 秒」不停循環。\(n\) 個小朋友各自在第 \(t_i\) 秒騎完一圈，騎完時若落在紅燈，就要等到這次紅燈結束。求所有人等待秒數的總和。（\(1 \le a, b \le 100\)、\(1 \le n \le 30\)、\(t_i \le 1000\)）

依正確通過的測試資料筆數給分，其中：

子題組 1（\(60\) 分）：\(a = b = 10\) 且 \(n = 1\)。
子題組 2（\(40\) 分）：無限制。

先拿下子題組 1（60 分）

子題組 1 保證 \(a = b = 10\) 而且 \(n = 1\)。這種「保證」可以直接寫進程式裡：讀完 \(a\)、\(b\)、\(n\) 之後，先用一個 if 判斷是不是子題組 1 的情況，是的話就用寫死 \(10\) 和 \(20\) 的最直覺寫法把它做掉。APCS 檢定初級光是把子題組 1 做出來，分數就相當高了，值得先把它拿穩。

想法：紅綠燈「綠 \(10\) 秒、紅 \(10\) 秒」一直重複，每 \(20\) 秒回到起點。所以騎完的時間 \(t\) 不管多大，都可以用 while 迴圈（4.2）「每滿 \(20\) 就扣 \(20\)」，把它折回第一個週期來看：

#include <iostream>
using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    if (a == 10 && b == 10 && n == 1) {   // 子題組 1：先把它拿穩
        int t;
        cin >> t;
        while (t >= 20) {      // 每滿一個週期（20 秒）就扣掉一個週期
            t = t - 20;
        }
        if (t >= 10) {
            cout << 20 - t << endl;   // 落在紅燈：等到這個週期結束
        } else {
            cout << 0 << endl;        // 落在綠燈：不用等
        }
    }
    return 0;
}

寫完拿範例 1 驗過（\(t = 14\) 折回後還是 \(14\)，紅燈，等 \(20 - 14 = 6\) 秒），再自己出幾筆小測資練邊界（都是 \(a = b = 10\)、一個人）：

\(t\)	折回第一個週期	位置	正確輸出
`9`	\(9\)	綠燈最後一秒	`0`
`10`	\(10\)	紅燈剛開始（題目的「註」說這種也要等）	`10`
`20`	\(0\)	剛好騎滿一個週期＝新週期綠燈開頭	`0`
`34`	\(14\)	紅燈中段	`6`

交這個版本時，範例 2 會顯示 WA（那筆 \(a = 4\)、\(b = 3\) 走不進 if，什麼都沒輸出）——這是正常的。APCS 逐筆給分，子題組 1 的 12 筆測資照樣全過，穩拿 60 分。

從 60 分到 100 分：while 迴圈也能拿滿分

不要以為 while 這種「暴力折回」的寫法只能拿子題組 1——它就是滿分解，只要把兩件事一般化：

週期不再寫死 \(20\)：改成 \(a + b\)；紅綠分界不再寫死 \(10\)：改成 \(a\)。
小朋友有 \(n\) 個：外面包一層 for 迴圈（4.3），一個人一個人算、把等待秒數加進總和。每個 \(t\) 用完就不會再用到，邊讀邊算就好，不需要陣列。

而且注意看下面的程式：剛剛那段子題組 1 的特判原封不動留著，一般解寫在 else 裡。這是考場上很值得養成的習慣——就算對滿分解沒有十足把握，也保留已經驗證過的部分分寫法：萬一一般解不小心寫錯了，子題組 1 那條路還是走原本對的程式，至少保住 60 分。

#include <iostream>
using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    if (a == 10 && b == 10 && n == 1) {   // 子題組 1：保留驗證過的保底寫法
        int t;
        cin >> t;
        while (t >= 20) {
            t = t - 20;
        }
        if (t >= 10) {
            cout << 20 - t << endl;
        } else {
            cout << 0 << endl;
        }
    } else {                              // 其他情況：一般解
        int total = 0;
        for (int i = 0; i < n; i++) {
            int t;
            cin >> t;
            while (t >= a + b) {       // 每滿一個週期就扣掉一個週期
                t = t - (a + b);
            }
            if (t >= a) {
                total = total + (a + b - t);   // 紅燈：等到週期結束
            }
        }
        cout << total << endl;
    }
    return 0;
}

會不會太慢？估一下：\(t \le 1000\)、週期至少 \(2\) 秒，所以內層 while 每個人最多扣 \(500\) 次，\(30\) 個人總共也才一萬多次——時限一秒內綽綽有餘。這一版交上去就是 \(100\) 分。（如果你已經很有把握——範例、自測都過——一般解本來就涵蓋子題組 1，特判拿掉也對；但保底策略在考場上永遠不吃虧。）

做完之後可以想一個進階問題：內層那個「一直減」的 while 迴圈，其實是在做一個你學過的運算。想想看要怎麼少一層迴圈？想通了再打開下面的 spoiler。

更簡潔的寫法：改用取餘運算

「把 \(t\) 每滿 \(a+b\) 就扣掉 \(a+b\)，直到小於 \(a+b\)」——這正是除以 \(a+b\) 取餘數在做的事，也就是 2.6 的 % 運算子。一行取代整個 while 迴圈：

int r = t % (a + b);   // t 落在週期中的第幾秒

之後的判斷完全一樣：

\(r < a\)：綠燈，等 \(0\) 秒。
\(r \ge a\)：紅燈，等 \(a + b - r\) 秒。注意是大於等於——\(r = a\) 是「紅燈剛好開始」，題目的「註」明說這種也要等（等滿 \(b\) 秒，公式 \(a + b - a = b\) 自動吻合，不用特判）。

這樣每個人只要固定幾步就算完（不再跟 \(t\) 的大小有關），整體時間複雜度 \(O(n)\)。順帶估一下數字大小：一個人最多等 \(a + b - 1 \le 199\) 秒，\(30\) 個人總和不超過 \(30 \times 199 = 5970\)，int 綽綽有餘。

常犯錯誤

條件寫成 t > a（或 r > a）漏了等號：折回週期後等於 \(a\) 是紅燈剛開始，也要等 \(b\) 秒。範例 2 的 25 就是專門考這個（折回後是 \(4 = a\)，要等 \(3\) 秒）——範例全過再交，就能自己抓到。
週期用錯：一個週期是 \(a + b\) 秒；while 版扣的、取餘版除的都要是 \(a + b\)，不是 \(a\) 也不是 \(b\)。
忘記先把 \(t\) 折回一個週期：直接拿原本的 \(t\) 跟 \(a\) 比較，\(t\) 一大就全錯。
忘記加總：答案是 \(n\) 個人的總和，只有一個輸出；不是每人各印一行，也不是只算第一個人。

參考程式碼（取餘版）

#include <iostream>
using namespace std;

int main() {
    int a, b, n;
    cin >> a >> b >> n;

    int total = 0;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        int r = t % (a + b);       // t 落在週期中的第幾秒
        if (r >= a) {
            total = total + (a + b - r);   // 紅燈：等到週期結束
        }
    }
    cout << total << endl;
    return 0;
}