商品包裝地 題解|APCS 2025 年 10 月中級 第 3 題
簡潔題意
\(N\) 筆 \(13\) 位數的商品條碼(\(N \le 100\)),前 \(3\) 碼是產地、第 \(13\) 碼是檢驗碼 \(C\)。前 \(12\) 位之中,奇數位置(\(1, 3, \ldots, 11\))的數字和是 \(S_{\text{odd}}\)、偶數位置(\(2, 4, \ldots, 12\))的數字和是 \(S_{\text{even}}\);滿足 \((S_{\text{odd}} + 3S_{\text{even}} + C) \bmod 10 = 0\) 的條碼才合法。只統計合法條碼,輸出出現最多次的產地(照原本的 \(3\) 位輸出)和它的合法條碼數。保證答案唯一。(APCS 逐筆給分。)
讀成字串,一位一位拆
條碼有 \(13\) 位,long long 放得下,但要一位一位拆、還要保留產地開頭的 \(0\),直接讀成 string 最方便。第 \(p\) 位的數字是 code[p - 1] - '0':題目的位置從 \(1\) 數起、字串的索引從 \(0\) 數起,字元減 '0' 得到它代表的數字。
合法條件用題目給的第二種寫法 (oddSum + 3 * evenSum + check) % 10 == 0,一個式子就判斷完;第一種寫法要同時接受「加起來是 \(0\)」和「加起來是 \(10\)」兩種情況。
產地存成字串,兩兩比對數次數
產地是 code.substr(0, 3),存成字串:轉成整數的話 030 會變成 \(30\),輸出時少了開頭的 \(0\)。
把每筆合法條碼的產地依序放進字串陣列 origins、用 total 記放了幾個(6.7),再對每一個產地數「有幾個跟它一樣」,用擂台留下最多的。\(N \le 100\),兩兩比對最多 \(10^4\) 次。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 105; // N ≤ 100
string origins[MAX_N]; // 每一筆合法條碼的產地(前 3 碼,照原樣存成字串)
int main() {
int n;
cin >> n;
int total = 0; // origins 裡放了幾個產地
for (int i = 0; i < n; i++) {
string code;
cin >> code;
int oddSum = 0, evenSum = 0;
for (int p = 1; p <= 12; p++) { // 題目的位置從 1 開始,字串索引從 0 開始
int digit = code[p - 1] - '0';
if (p % 2 == 1) oddSum += digit;
else evenSum += digit;
}
int check = code[12] - '0';
if ((oddSum + 3 * evenSum + check) % 10 == 0) {
origins[total] = code.substr(0, 3);
total++;
}
}
string bestOrigin = "";
int bestCount = 0;
for (int i = 0; i < total; i++) { // 每個產地數一次:有幾筆合法條碼跟它同產地
int count = 0;
for (int j = 0; j < total; j++) {
if (origins[j] == origins[i]) count++;
}
if (count > bestCount) {
bestCount = count;
bestOrigin = origins[i];
}
}
cout << bestOrigin << " " << bestCount << endl;
}
測過再交:範例四筆全部合法
範例的四筆條碼都合法、答案的產地也沒有開頭的 \(0\),不檢查檢驗碼也會對。下面五種錯法範例都會過(見常犯錯誤),自己補這幾筆:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
3/4710000000000/4710000000001/3000000000007 |
300 1 |
471 出現最多次,但兩筆都不合法 |
2/0300000000001/0301111111112 |
030 2 |
產地開頭是 \(0\) |
1/2220000000000 |
222 1 |
加起來剛好是 \(0\) 的合法條碼;只有一筆合法條碼 |
三筆都親眼看過正確,這題就穩了。
常犯錯誤
- 用全部條碼的筆數挑產地,挑好再數合法的:範例全過,自測表第 1 列印
471 0;本站 \(20\) 筆掛 \(17\) 筆。 - 完全沒檢查檢驗碼:範例四筆都合法,所以全過;自測表第 1 列印
471 2,本站 \(20\) 筆掛 \(18\) 筆。 - 只照第一種寫法接受「加起來是 \(10\)」,漏了「加起來是 \(0\)」:範例全過,自測表第 3 列印不出產地;本站 \(20\) 筆掛 \(7\) 筆。
- 產地轉成整數:範例全過,自測表第 2 列印
30 2;本站 \(20\) 筆掛 \(7\) 筆。 - 排序後數「連續相同的有幾個」,擂台初值設 \(0\)、迴圈從第二筆開始比:只有一筆合法條碼時迴圈一次都不跑,自測表第 3 列印
222 0。範例全過;本站 \(20\) 筆掛 \(7\) 筆。