Editorial for hex2dec: Đổi hệ cơ số 16 sang hệ thập phân

Hiểu bài toán

Bài toán yêu cầu chuyển đổi một số nguyên dương từ hệ cơ số 16 (thập lục phân) sang hệ cơ số 10 (thập phân). Input gồm nhiều test case, mỗi test là một số ở hệ 16, có thể chứa các ký tự từ '0'-'9' và 'A'-'F'. Số này có tối đa 16 ký tự, tương đương giá trị tối đa là 16^16 - 1, nằm trong phạm vi của kiểu số nguyên 64-bit (long long).

Các cách tiếp cận

Cách Chuyển đổi trực tiếp khi đọc chuỗi (Làm tròn về 0)

#include <stdio.h>
#include <string.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char s[20];
        scanf("%s", s);
        long long result = 0;
        for (int i = 0; s[i] != '\0'; i++) {
            char c = s[i];
            int val;
            if (c >= '0' && c <= '9') val = c - '0';
            else val = c - 'A' + 10;
            result = result * 16 + val;
        }
        printf("%lld\n", result);
    }
    return 0;
}

• Time Complexity: O(N) với N là độ dài chuỗi
• Space Complexity: O(1)

Thuật toán duyệt qua từng ký tự của chuỗi số hệ 16. Với mỗi ký tự, ta chuyển nó về giá trị số (0-15). Sau đó, ta cập nhật kết quả bằng cách nhân kết quả hiện tại với 16 (tương đương dịch trái 4 bit) rồi cộng với giá trị của ký tự mới. Ví dụ: '1A' -> result = 016 + 1 = 1; result = 116 + 10 = 26. Cách này hiệu quả và chỉ cần duyệt qua chuỗi một lần.

Cách Xử lý từ phải sang trái (Làm tròn về 0)

#include <stdio.h>
#include <string.h>

#define ll long long

ll hexToDec(char *s) {
    ll n = strlen(s);
    ll ans = 0;
    ll base = 1;
    for (int i = n - 1; i >= 0; i--) {
        char c = s[i];
        int val;
        if (c >= '0' && c <= '9') val = c - '0';
        else val = c - 'A' + 10;
        ans += val * base;
        base *= 16;
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char s[20];
        scanf("%s", s);
        printf("%lld\n", hexToDec(s));
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Cách tiếp cận này duyệt chuỗi từ ký tự cuối cùng (phải) về ký tự đầu tiên (trái). Nó tính toán giá trị của từng chữ số và nhân với cơ số 16 tương ứng (1, 16, 256, ...). Kết quả cuối cùng là tổng các giá trị này. Ví dụ: '1A' -> (10 * 1) + (1 * 16) = 26. Tuy logic nhưng cách này cần lưu trữ biến 'base' (cơ số lũy thừa) và thường phức tạp hơn một chút so với cách duyệt từ trái sang phải.

Cách Sử dụng hàm chuyển đổi có sẵn (C++ hoặc Python)

#include <iostream>
#include <string>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    while (t--) {
        std::string s;
        std::cin >> s;
        // std::stoll tự động chuyển đổi chuỗi hệ 16 sang số
        std::cout << std::stoll(s, nullptr, 16) << "\n";
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Trong các kỳ thi thực tế (nếu ngôn ngữ được chọn là C++), cách nhanh nhất là sử dụng thư viện chuẩn. Hàm std::stoll (string to long long) có thể nhận thêm tham số thứ 3 là hệ cơ số (16). Cách này ngắn gọn, dễ đọc và đã được tối ưu hóa.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Các ký tự 'A' đến 'F' tương ứng với giá trị 10 đến 15. Có thể chuyển đổi bằng công thức: c - 'A' + 10.
• Kiểu dữ liệu long long (64-bit) ở C/C++ có thể lưu trữ số lên đến ~9 * 10^18, đủ để chứa giá trị lớn nhất của số hệ 16 có 16 ký tự (16^16 ~ 1.8 * 10^19, nhưng đề bài giới hạn n <= 10^18).
• Phép cộng dồn (result = result * 16 + val) là cách hiệu quả nhất để tính toán trong khi duyệt chuỗi.

Lỗi thường gặp

• Quên xử lý các ký tự viết hoa 'A'-'F', hoặc nhầm lẫn giữa 'A' (10) và 'a' (10) nếu input có thể chứa chữ thường (mặc dù đề bài chỉ ghi 'A').
• Sử dụng kiểu int hoặc long (32-bit) để lưu trữ kết quả cuối cùng, dẫn đến tràn số (overflow) vì 10^18 lớn hơn giới hạn 2^31 - 1.
• Quên in dấu newline '\n' sau mỗi kết quả.