秘密差 題解|APCS 2017 年 3 月中級 第 1 題


簡潔題意

給一個十進位正整數 \(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.10 的用法 1一模一樣的題目:% 10 抓出尾巴那一位、/ 10 把尾巴砍掉,組合出每一位。四位數的奇數位就是個位+百位、偶數位是十位+千位,拆出來加一加、相減,差是負的就把它變號(一個 if 就是手工版的絕對值),\(20\) 分到手:

#include <iostream>
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 位)

    int diff = (d1 + d3) - (d2 + d4);   // 奇數位和 - 偶數位和
    if (diff < 0) diff = -diff;         // 負的就變號(手工絕對值)
    cout << diff << 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>
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;
    }

    int diff = sum1 - sum2;       // 兩組和的差
    if (diff < 0) diff = -diff;   // 負的就變號(手工絕對值)
    cout << diff << endl;
    return 0;
}

拿範例 1 走一遍:\(263541\) 依序拆出 \(1, 4, 5, 3, 6, 2\),交替加成 \(A = 1 + 5 + 6 = 12\)、\(B = 4 + 3 + 2 = 9\),\(|12 - 9| = 3\)。這一版兩個範例都會全過,前兩個子題組的測資也都過得了。

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

想多練這兩個子題組的寫法,可以做〈秘密差(簡化版)〉:\(X\) 最多 \(18\) 位,只用上冊第四單元為止的語法就能拿滿分。

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

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

這一步要轉的彎不小:前兩個子題組都把 \(X\) 當成一個數來拆,滿分卻要整個換一種讀法。

回頭看整個過程:我們從頭到尾沒有把 \(X\) 當成一個數做過任何加減乘除——只是把它的每一位數字逐一看過去。既然如此,\(X\) 根本不必住在數字型態裡:把它當成字串整個讀進來就好。string要多長就能多長,\(1000\) 位也裝得下:

  • string x; cin >> x; 把 \(X\) 整串讀進來,x.size() 就是位數 \(n\)。
  • x[i] 是從左邊數第 \(i\) 個字元(從 \(0\) 數起),它是字元 '5',不是數字 \(5\)。換成數值要減掉 '0':x[i] - '0'(數字字元跟 '0' 的距離,就是它代表的數值)。
  • 題目的奇偶位是從右邊數的。最右邊的 x[n - 1] 是右起第 \(1\) 位,往左一格加一:x[i] 是右起第 \(n - i\) 位,所以 (n - i) % 2 == 1 的那些是奇數位。
#include <iostream>
#include <string>
using namespace std;

int main() {
    string x;
    cin >> x;                     // 整個 X 當成字串讀進來,1000 位也裝得下
    int n = x.size();             // 位數

    int sum1 = 0, sum2 = 0;       // sum1=奇數位的和、sum2=偶數位的和
    for (int i = 0; i < n; i++) {
        int d = x[i] - '0';       // 數字字元換成它代表的數值
        if ((n - i) % 2 == 1) {   // x[i] 是右起第 n - i 位
            sum1 = sum1 + d;
        } else {
            sum2 = sum2 + d;
        }
    }

    int diff = sum1 - sum2;       // 兩組和的差
    if (diff < 0) diff = -diff;   // 負的就變號(手工絕對值)
    cout << diff << endl;
    return 0;
}

拿範例 1 對一次:263541 的 \(n = 6\),x[5] 是 '1'(右起第 \(1\) 位,奇數位),x[0] 是 '2'(右起第 \(6\) 位,偶數位)——跟題目從右數的定義一致,\(A = 1 + 5 + 6 = 12\)、\(B = 4 + 3 + 2 = 9\),答案 \(3\)。

位數和最大也不過 \(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 + x[i],加進去的是字元的編號('0' 是 \(48\)),不是它代表的數字。最陰的地方在於:位數是偶數時答案照樣對——每個數字都多算了 \(48\),兩組位數一樣多時,多算的部分相減剛好抵消,範例 1(六位)就這樣矇對了;位數是奇數才現形,範例 2(三位)會輸出 \(47\)。兩個範例一起餵才抓得到。
  3. 迴圈寫成 i <= n:多跑一圈去拿 x[n],那裡已經不是 \(X\) 的數字了,換算出來是 \(-48\),硬是被加進其中一組。範例 1 會輸出 \(51\),當場抓到。
  4. 忘了取絕對值:\(A < B\) 時會輸出負數,範例 2 就會輸出 \(-1\),當場抓到。
  5. 被「輸入包含若干筆測試資料」嚇到:這是 APCS 評分說明的固定格式,意思是評測會拿很多筆測資檔逐一執行你的程式,不是一次執行要處理很多個 \(X\)——輸入格式明說只有一行一個正整數,照單筆處理就好。