商品包裝地 題解|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\) 筆。