秘密差 題解|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 極限,專驗有沒有真的當字串讀 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 用整數型態讀 \(X\):兩個範例都照樣全過、前兩個子題組也全過——只有 \(1000\) 位的子題組 3 全錯,而且
long long(最多 \(19\) 位)一樣不夠。「範例全過」給的安全感在這題特別虛:上面自測表最後一筆(\(22\) 個 \(9\))餵下去,int版會印出 \(12\) 這種莫名其妙的數字,當場現形。 - 忘了減
'0':直接sum1 = sum1 + x[i],加進去的是字元的編號('0'是 \(48\)),不是它代表的數字。最陰的地方在於:位數是偶數時答案照樣對——每個數字都多算了 \(48\),兩組位數一樣多時,多算的部分相減剛好抵消,範例 1(六位)就這樣矇對了;位數是奇數才現形,範例 2(三位)會輸出 \(47\)。兩個範例一起餵才抓得到。 - 迴圈寫成
i <= n:多跑一圈去拿x[n],那裡已經不是 \(X\) 的數字了,換算出來是 \(-48\),硬是被加進其中一組。範例 1 會輸出 \(51\),當場抓到。 - 忘了取絕對值:\(A < B\) 時會輸出負數,範例 2 就會輸出 \(-1\),當場抓到。
- 被「輸入包含若干筆測試資料」嚇到:這是 APCS 評分說明的固定格式,意思是評測會拿很多筆測資檔逐一執行你的程式,不是一次執行要處理很多個 \(X\)——輸入格式明說只有一行一個正整數,照單筆處理就好。