Editorial for 秘密差 (APCS 2017-03 初級)


簡潔題意

給一個十進位正整數 \(X\),把奇數位(右起第 \(1, 3, 5, \ldots\) 位)的數字加起來叫 \(A\)、偶數位的數字和叫 \(B\),輸出秘密差 \(|A - B|\)。

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

  • 子題組 1(\(20\) 分):\(X\) 恰好四位數。
  • 子題組 2(\(30\) 分):\(X\) 的位數不超過 \(9\)。
  • 子題組 3(\(50\) 分):\(X\) 的位數不超過 \(1000\)。

子題 1(20 分):恰好四位數,用 % 和 / 直接拆

子題組 1 保證 \(X\) 恰好是四位數——而「把一個四位數的千、百、十、個位分別拆出來」,正是 2.6 的套路 1一模一樣的題目:% 10 抓出尾巴那一位、/ 10 把尾巴砍掉,組合出每一位。四位數的奇數位就是個位+百位、偶數位是十位+千位,拆出來加一加、取絕對差,\(20\) 分到手:

#include <iostream>
#include <cstdlib>     // abs 住在這(上冊 7.6)
using namespace std;

int main() {
    int x;
    cin >> x;                      // 子題 1 保證恰好四位數

    int d1 = x % 10;               // 個位(右起第 1 位)
    int d2 = x / 10 % 10;          // 十位(右起第 2 位)
    int d3 = x / 100 % 10;         // 百位(右起第 3 位)
    int d4 = x / 1000;             // 千位(右起第 4 位)

    cout << abs((d1 + d3) - (d2 + d4)) << endl;   // |奇數位和 - 偶數位和|
    return 0;
}

子題 2(30 分):位數不固定,進化成 while 逐位拆

子題組 2 的位數「不超過 \(9\)」——不固定幾位,寫死四行拆不動了。這個進化語法書也帶你走過:4.2範例 3〈計算位數總和〉做的就是這件事——「位數不固定時就得靠迴圈:每圈撈出最後一位、再把最後一位切掉,切到變成 \(0\) 為止」。本題只比它多一件事:撈出來的數字交替分進兩組。位數不超過 \(9\) 表示 \(X\) 最大 \(999999999\),塞進 int(上限約 \(2.1 \times 10^9\),2.9 的範圍表)綽綽有餘。而且這樣拆有個天生的好處:第一個拆出來的就是個位=右起第 \(1\) 位=奇數位,之後每拆一位交替一次,跟題目的定義嚴絲合縫:

#include <iostream>
#include <cstdlib>     // abs 住在這(上冊 7.6)
using namespace std;

int main() {
    int x;
    cin >> x;

    int sum1 = 0, sum2 = 0;   // sum1=右起第 1、3、5…位;sum2=右起第 2、4、6…位
    bool odd = true;          // 個位是右起第 1 位:奇數位
    while (x > 0) {
        int d = x % 10;       // 拆出目前的個位
        if (odd) {
            sum1 = sum1 + d;
        } else {
            sum2 = sum2 + d;
        }
        x = x / 10;           // 丟掉個位
        odd = !odd;
    }

    cout << abs(sum1 - sum2) << endl;   // 兩組和的絕對差
    return 0;
}

拿範例 1 走一遍:\(263541\) 依序拆出 \(1, 4, 5, 3, 6, 2\),交替加成 \(A = 1 + 5 + 6 = 12\)、\(B = 4 + 3 + 2 = 9\),\(|12 - 9| = 3\)。這一版兩個範例都會全過,交上去照子題組的設計能拿下前兩組合計 \(50\) 分的範圍。

到這裡用的全部都是語法書上冊教過的東西——2.6 的套路 1、4.2 的範例 3,一路都是課本親自帶你寫過的程式。語法書有好好讀的話,這題至少前兩個子題一定做得出來。

但注意:範例全過,不代表它是滿分解。子題組 3 的 \(X\) 可以長達 \(1000\) 位——int 塞不下,換成 long long 也只能到 \(19\) 位(2.9),離 \(1000\) 位差得遠。想滿分,需要換一個角度看 \(X\)。

從 50 分到 100 分:X 不是拿來算的,把它當文字讀

先說一件特別的事:在 APCS 初級的考古題裡,這是唯一一題只靠語法書上冊的知識拿不到滿分的題目。卡在這裡不是你的問題——這是 APCS 剛開始舉辦時的題目,當年題目的難度與類型都還沒定下來,前幾場常常發生前面的題目太難、或後面的題目太簡單之類的情形。接下來要用的技巧屬於下冊的範圍,我們會把道理講清楚,先看懂就能用。

回頭看整個過程:我們從頭到尾沒有把 \(X\) 當成一個數做過任何加減乘除——只是把它的每一位數字逐一看過去。既然如此,\(X\) 根本不必住在數字型態裡:把它當一串文字、一個字元一個字元讀進來就好。讀法用 4.8 教過的模式:

char c;
while (cin >> c) {   // 一次讀一個字元,讀到沒有輸入為止
    ...
}

字元怎麼變回數字?2.4 說過每個字元背後都有一個編號,而數字字元 '0''9' 的編號是連著排的——所以 c - '0'(兩個編號相減)正好就是 c 代表的數字:'7' - '0' 等於 \(7\)。這一行用到的正是下冊 8.2 的〈數字字元 ↔ 數值〉正式教的知識。想真正把它學會的人,建議提前把下冊第八單元從 8.1〈字元的本質:ASCII 編碼〉讀起——字元的本質弄懂之後,這一行就完全不神祕了。

還有一個看起來麻煩、其實完全不用管的問題:逐字元是從左邊讀起的,題目的奇偶位卻是從右邊數——要不要先知道總長度來換算?不用。交替分組永遠把數字切成同樣的兩堆,「從哪邊開始數」只決定哪一堆 \(A\)、哪一堆 \(B\);而秘密差取的是絕對值,\(|A - B|\) 和 \(|B - A|\) 一樣——兩堆對調,答案不變。拿範例 1 驗證:\(263541\) 從左交替分成 \(\{2, 3, 4\} = 9\) 和 \(\{6, 5, 1\} = 12\),\(|9 - 12| = 3\),跟題目從右數的算法一模一樣。

於是滿分解連陣列都不用開,邊讀邊加就好:

#include <iostream>
#include <cstdlib>     // abs 住在這(上冊 7.6)
using namespace std;

int main() {
    int sum1 = 0, sum2 = 0;   // 交替的兩組位數和
    bool first = true;        // 這個字元屬於第一組嗎
    char c;
    while (cin >> c) {        // 一次讀一個字元,讀到沒有輸入為止(4.8)
        int d = c - '0';      // 數字字元的編號連著排:'7' 的編號減 '0' 的編號就是 7
        if (first) {
            sum1 = sum1 + d;
        } else {
            sum2 = sum2 + d;
        }
        first = !first;
    }

    cout << abs(sum1 - sum2) << endl;   // 兩組和的絕對差
    return 0;
}

位數和最大也不過 \(1000 \times 9 = 9000\),int 隨便裝。

測過再交:範例根本測不出「長數」

兩個範例一個 \(6\) 位、一個 \(3\) 位——連 int 版都全過。你的程式能不能真的吃下 \(1000\) 位,範例完全測不出來。自己補幾筆,重點是造一個「長度超過 \(19\) 位」的數(超出 long long 的極限):挑全部同一個數字的長串,答案可以口算——比如 \(22\) 個 \(9\),兩組各分到 \(11\) 個 \(9\),秘密差是 \(0\)。

輸入 正確輸出 這一筆在測什麼
7 7 一位數:其中一組是空的
1234 2 恰四位數(子題組 1 本人):\(A = 4 + 2\)、\(B = 3 + 1\)
11 0 兩組相等,秘密差為 \(0\)
9999999999999999999999 0 \(22\) 個 \(9\):長度超過 long long 極限,專驗有沒有真的當文字讀

四筆都親眼看過正確,這題就穩了。

常犯錯誤
  1. 用整數型態讀 \(X\):兩個範例都照樣全過、前兩個子題組也全過——只有 \(1000\) 位的子題組 3 全錯,而且 long long(最多 \(19\) 位)一樣不夠。「範例全過」給的安全感在這題特別虛:上面自測表最後一筆(\(22\) 個 \(9\))餵下去,int 版會印出 \(12\) 這種莫名其妙的數字,當場現形。
  2. 忘了減 '0':直接 sum1 = sum1 + c 加進去的是字元編號不是數字。最陰的地方在於:位數是偶數時,兩組各含一樣多的編號底數、相減恰好抵消,答案照樣對——範例 1(六位)就這樣矇對了;位數是奇數才現形,範例 2(三位)會輸出 \(47\)。兩個範例一起餵才抓得到。
  3. 忘了取絕對值:\(A < B\) 時會輸出負數——範例 1 輸出 \(-3\)、範例 2 輸出 \(-1\),範例當場抓到。像主文那樣用 abs()7.6)一行搞定;自己用 if 把負數翻正也行。
  4. EOF 迴圈寫成 while (!cin.eof())eof()讀取失敗之後才會變成真——「先檢查、再讀取」的寫法,最後一次讀取失敗時 c 還留著上一個字元、會被多加一次:範例 1 會輸出 \(2\)(正確是 \(3\))。照 4.8 的正規寫法 while (cin >> c) 就沒事。
  5. 被「輸入包含若干筆測試資料」嚇到:這是 APCS 評分說明的固定格式,意思是評測會拿很多筆測資檔逐一執行你的程式,不是一次執行要處理很多個 \(X\)——輸入格式明說只有一行一個正整數,照單筆處理就好。