Editorial for digit5: Số chữ số 5

Hiểu bài toán

Bài toán yêu cầu đếm tổng số lần xuất hiện của chữ số '5' trong tất cả các số nguyên từ M đến N (bao gồm cả M và N). Ví dụ, với dãy 5, 15, 50, số lần xuất hiện chữ số '5' là 1 (từ số 5), 1 (từ số 15), và 2 (từ số 50), tổng cộng là 4. Với ràng buộc N - M ≤ 10^5, ta có thể xử lý từng số trong khoảng này, nhưng với N có thể lên tới 10^9, cần một phương pháp tối ưu hơn cho các bài toán tổng quát.

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

Cách Brute Force (Duyệt từng số)

#include <stdio.h>

int count_digits_5(int n) {
    int count = 0;
    while (n > 0) {
        if (n % 10 == 5) count++;
        n /= 10;
    }
    return count;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int total = 0;
    for (int i = a; i <= b; i++) {
        total += count_digits_5(i);
    }
    printf("%d", total);
    return 0;
}

• Time Complexity: O((N - M) * log N)
• Space Complexity: O(1)

Phương pháp này duyệt qua từng số i từ M đến N. Với mỗi số i, hàm count_digits_5 lặp qua các chữ số của nó (thường là log10(N) lần) và đếm số lần chữ số 5 xuất hiện. Do giới hạn N - M ≤ 10^5, số lượng số cần duyệt là 10^5, mỗi số có tối đa 10 chữ số. Phương pháp này đơn giản và dễ hiểu, hoàn toàn khả thi với ràng buộc N - M ≤ 10^5.

Cách Quy hoạch động theo chữ số (Digit DP)

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

long long cnt5(long long x) {
    if (x <= 0) return 0;
    long long count = 0;
    // Duyệt qua từng vị trí chữ số từ phải sang trái (units, tens, hundreds...)
    for (long long p = 1; p <= x; p *= 10) {
        long long left = x / (p * 10);  // Phần bên trái vị trí hiện tại
        long long digit = (x / p) % 10; // Chữ số tại vị trí hiện tại
        long long right = x % p;        // Phần bên phải vị trí hiện tại

        if (digit < 5) {
            // Nếu chữ số hiện tại nhỏ hơn 5, số lượng số có chữ số 5 tại vị trí này
            // bằng số lượng tổ hợp của các chữ số bên trái nhân với kích thước bước (p)
            count += left * p;
        } else if (digit == 5) {
            // Nếu bằng 5, bao gồm các số có chữ số 5 ở các tổ hợp bên trái nhỏ hơn
            // và các số bắt đầu bằng phần bên trái hiện tại + 5 + phần bên phải
            count += left * p + right + 1;
        } else {
            // Nếu lớn hơn 5, bao gồm cả trường hợp chữ số bên trái tăng thêm 1
            count += (left + 1) * p;
        }
    }
    return count;
}

int main() {
    long long m, n;
    scanf("%lld %lld", &m, &n);
    // Số lượng chữ số 5 từ 1 đến N trừ đi số lượng từ 1 đến M-1
    printf("%lld", cnt5(n) - cnt5(m - 1));
    return 0;
}

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

Đây là phương pháp tối ưu, tính số lần xuất hiện của chữ số 5 trong khoảng từ 1 đến X trong thời gian logarit. Công thức tính cho mỗi vị trí chữ số (bậc 10^k):

1. Xác định phần bên trái (left), chữ số hiện tại (digit), và phần bên phải (right).
2. Nếu digit < 5: Số lượng số có chữ số 5 tại vị trí này là left * 10^k.
3. Nếu digit == 5: Số lượng là left * 10^k + right + 1.
4. Nếu digit > 5: Số lượng là (left + 1) * 10^k. Tổng hợp lại ta得到 hàm cnt5(x). Kết quả cho bài toán là cnt5(N) - cnt5(M-1). Phương pháp này cực kỳ hiệu quả và giải quyết được mọi test case trong giới hạn đề bài.

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

Bài học kinh nghiệm

• Số lần xuất hiện của một chữ số tại một vị trí c cụ thể có thể được tính toán bằng cách xem xét các chữ số bên trái và bên phải của nó.
• Bài toán đếm số lần xuất hiện trong khoảng [M, N] có thể quy về bài toán tính hàm đếm từ 1 đến X rồi lấy hiệu: F(N) - F(M-1).

Lỗi thường gặp

• Sử dụng biến int cho các biến đếm hoặc số lớn, dẫn đến tràn số (overflow) khi N lên tới 10^9. Cần dùng long long.
• Xử lý sai trường hợp số 0 hoặc số có chứa nhiều chữ số 5 liên tiếp trong phương pháp quy hoạch động.
• Lặp quá nhiều số khi N - M lớn (nếu chỉ dùng phương pháp duyệt thường) gây TLE.