Hiểu bài toán

Yêu cầu: Đếm số lượng số 'đẹp' trong khoảng [l, r]. Một số được coi là đẹp nếu nó vừa là số đối xứng (palindrome) và tổng các chữ số của nó chia hết cho 10.

Đầu vào: Nhiều test cases, mỗi test gồm 2 số l, r. Đầu ra: Số lượng số đẹp trong mỗi test.

Ràng buộc:

• Số test <= 10^4.
• 1 <= l <= r <= 10^9.
• r - l <= 10^4 (khoảng cách giữa l và r rất nhỏ).

Ví dụ: [1, 10] -> 0 số đẹp; [11, 100] -> 1 số đẹp (số 22: palindrome và 2+2=4 không chia hết 10? Wait, sample output 1. 11 là palindrome nhưng 1+1=2. 22: 2+2=4. 33: 3+3=6. 44: 4+4=8. 55: 5+5=10 chia hết 10. Vậy 55 là số đẹp. Kiểm tra lại Sample Output: Output là 1. Trong đoạn [11, 100], chỉ có 55 là thỏa mãn tổng chữ số chia hết 10. Đúng vậy.

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

Cách Brute Force (Duyệt khoảng)

#include <stdio.h>

int is_palindrome(int n) {
    int original = n, reversed = 0;
    while (n > 0) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return original == reversed;
}

int digit_sum_divisible_by_10(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum % 10 == 0;
}

int main() {
    int l, r;
    while (scanf("%d %d", &l, &r) != EOF) {
        int count = 0;
        for (int i = l; i <= r; i++) {
            if (is_palindrome(i) && digit_sum_divisible_by_10(i)) {
                count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

• Time Complexity: O((r-l) * log(r))
• Space Complexity: O(1)

Đây là cách giải quyết trực tiếp nhất. Với mỗi test case, ta duyệt qua từng số i từ l đến r. Với mỗi số i, ta kiểm tra 2 điều kiện:

1. Có phải là số đối xứng không: Đảo ngược các chữ số của i và so sánh với i ban đầu.
2. Tổng các chữ số có chia hết cho 10 không: Tính tổng các chữ số và kiểm tra tính chia hết.

Do r - l <= 10^4, số lượng số cần duyệt trong mỗi test rất nhỏ (tối đa 10,001 số). Độ phức tạp xử lý mỗi số là O(log i) (số lượng chữ số). Tổng độ phức tạp khoảng 10^4 * 10 = 10^5 phép toán mỗi test, hoàn toàn đáp ứng thời gian với 10^4 test cases.

Cách Brute Force (Code ngắn gọn)

#include <stdio.h>
#include <stdbool.h>

bool isBeautiful(int n) {
    int sum = 0, temp = n, rev = 0;
    while (temp > 0) {
        int digit = temp % 10;
        sum += digit;
        rev = rev * 10 + digit;
        temp /= 10;
    }
    return (rev == n && sum % 10 == 0);
}

int main() {
    int l, r;
    while (scanf("%d %d", &l, &r) == 2) {
        int cnt = 0;
        for (int i = l; i <= r; i++) {
            if (isBeautiful(i)) cnt++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

• Time Complexity: O((r-l) * log(r))
• Space Complexity: O(1)

Cách tiếp cận này về cơ bản giống giải pháp 1 nhưng được tối ưu hóa mã nguồn. Thay vì tách biệt hàm kiểm tra palindrome và tổng chữ số, ta kết hợp cả hai trong một hàm isBeautiful. Khi duyệt qua các chữ số của số để tính tổng, ta cũng đồng thời tạo ra số đảo ngược. Điều này giúp giảm một nửa số lần duyệt qua các chữ số, tối ưu hơn một chút về tốc độ chạy thực tế.

Cách Tăng tốc Brute Force (Duyệt theo bước nhảy)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool isPalindrome(int n) {
    string s = to_string(n);
    string rs = s;
    reverse(rs.begin(), rs.end());
    return s == rs;
}

int getSum(int n) {
    int s = 0;
    while (n > 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}

int main() {
    int l, r;
    while (cin >> l >> r) {
        int count = 0;
        for (int i = l; i <= r; i++) {
            if (isPalindrome(i) && getSum(i) % 10 == 0) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

• Time Complexity: O((r-l) * log(r))
• Space Complexity: O(1)

Giải pháp này sử dụng C++ và thư viện string để kiểm tra đối xứng một cách dễ dàng. Tuy nhiên, về bản chất thuật toán vẫn là duyệt toàn bộ khoảng [l, r]. Trong ngữ cảnh bài toán này với r-l nhỏ, cách này chạy rất nhanh. Tuy nhiên, để thực sự tối ưu hóa Brute Force, ta có thể nhận thấy rằng số đối xứng khá hiếm. Ta có thể chỉ duyệt các số đối xứng trong khoảng [l, r] thay vì duyệt tất cả các số.

Phương pháp tối ưu hóa Brute Force (Duyệt số đối xứng):

• Tạo ra các số đối xứng trong khoảng [l, r] và kiểm tra tổng chữ số.
• Số đối xứng có thể được tạo ra từ một nửa của nó. Ví dụ: 121 được tạo từ 12.
• Tuy nhiên, do r-l nhỏ, việc tạo ra tất cả số đối xứng và lọc theo khoảng có thể phức tạp hơn so với việc chỉ đơn giản duyệt và kiểm tra 10,000 số.

Lưu ý: Các solution mẫu đều sử dụng Brute Force bình thường do ràng buộc r-l <= 10^4.

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

Bài học kinh nghiệm

• Ràng buộc 'r - l <= 10^4' là chìa khóa. Nó cho phép sử dụng thuật toán duyệt đơn giản (Brute Force) trực tiếp trên khoảng [l, r] mà không cần phải sinh số đối xứng trước.
• Một số đối xứng có tổng chữ số chia hết cho 10 là khá hiếm, nhưng việc kiểm tra nhanh (mỗi số chỉ mất khoảng 10-12 thao tác tính toán) đảm bảo hiệu năng.
• Kiểm tra palindrome và tính tổng chữ số có thể được kết hợp trong một vòng lặp duy nhất để tối ưu nhẹ.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai: Nếu l và r lên tới 10^9, cần dùng int (32-bit) là đủ, nhưng long long an toàn hơn. Tuy nhiên, khi đảo ngược số, nếu số quá lớn (ví dụ 10^18), long long có thể tràn số nếu không xử lý đúng (với 10^9 thì long long an toàn tuyệt đối).
• Độ chính xác của phép chia: Trong C/C++, phép chia số nguyên với số âm có thể gây sai sót nếu không cẩn thận, nhưng đề bài cho biết l, r là số nguyên dương nên không gặp vấn đề này.
• Xử lý nhiều test cases: Cần đảm bảo vòng lặp while(scanf(...) != EOF) hoặc while(cin >> ...) được viết đúng để xử lý toàn bộ đầu vào.