ZOJ Martian Addition：20 進制大數加法模擬

ZOJ Martian Addition：20 進制大數加法

火星人有 20 根手指，使用 20 進制。數字 0-9, a-j 表示 0-19。給定兩個不超過 100 位的 20 進制數，求其和。

解題思路

• 字符映射：'0'-'9' → 0-9, 'a'-'j' → 10-19。
• 逆序存儲數字數組，模擬小學加法：逐位相加，處理進位。
• 結果逆序輸出，映射回字符。

字符映射表

char toChar[20] = {'0','1','2','3','4','5','6','7','8','9',
                   'a','b','c','d','e','f','g','h','i','j'};
int toVal(char c) {
    if(c >= '0' && c <= '9') return c - '0';
    return c - 'a' + 10;
}

代碼實現（C++）

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    string s1, s2;
    while(cin >> s1 >> s2) {
        int a[105] = {0}, b[105] = {0}, c[105] = {0};
        int n1 = s1.size(), n2 = s2.size();
        for(int i = 0; i < n1; i++) a[i] = toVal(s1[n1-1-i]);
        for(int i = 0; i < n2; i++) b[i] = toVal(s2[n2-1-i]);
        
        int len = max(n1, n2), carry = 0;
        for(int i = 0; i < len || carry; i++) {
            int sum = a[i] + b[i] + carry;
            c[i] = sum % 20;
            carry = sum / 20;
            len = max(len, i+1);
        }
        while(len > 1 && c[len-1] == 0) len--; // 去除前導零
        for(int i = len-1; i >= 0; i--) cout << toChar[c[i]];
        cout << '\n';
    }
    return 0;
}

樣例演示

輸入:
1234567890 abcdefghij
99999jjjjj 9999900001

輸出:
bdfi02467j
iiiij00000

關鍵點

• 進制固定為 20，進位邏輯簡單。
• 數組大小 105 足夠（100 位 + 進位）。
• 輸出時去除前導零，但至少保留一位。

複雜度

O(max(len1, len2))，線性時間。

總結

大數加法模擬的經典變體，僅進制從 10 變為 20。字符映射與進位處理是核心。