Editorial for xepso2: Xếp số bằng que diêm 2

Hiểu bài toán

Bài toán yêu cầu tìm số que diêm ít nhất và nhiều nhất cần thiết để biểu diễn một số nguyên nằm trong đoạn số [L, R] cho trước. Với mỗi số, ta có thể đếm số que diêm cần thiết bằng cách sử dụng mảng quy ước: [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] tương ứng với các chữ số 0-9. Với mỗi số trong đoạn [L, R], ta tính tổng số que diêm của tất cả các chữ số, sau đó tìm giá trị nhỏ nhất (a) và lớn nhất (b) trong các tổng đó. Ràng buộc quan trọng là R - R <= 10^5, nghĩa là số lượng số cần kiểm tra trong mỗi test case không lớn, cho phép duyệt qua từng số.

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

Cách Brute Force (Duyệt toàn bộ)

#include <bits/stdc++.h>
using namespace std;

int match[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int countMatch(long long num) {
    int res = 0;
    if (num == 0) return match[0];
    while (num) {
        res += match[num % 10];
        num /= 10;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        long long L, R; cin >> L >> R;
        int mn = INT_MAX, mx = INT_MIN;
        for (long long i = L; i <= R; i++) {
            int c = countMatch(i);
            mn = min(mn, c);
            mx = max(mx, c);
        }
        cout << mn << " " << mx << "\n";
    }
}

• Time Complexity: O(T * (R-L) * log10(R)) do R-L <= 10^5 và số chữ số tối đa ~18.
• Space Complexity: O(1)

Đây là phương pháp trực tiếp nhất. Với mỗi test case, ta duyệt qua từng số i từ L đến R. Hàm countMatch thực hiện việc tách từng chữ số của i và cộng dồn số que diêm tương ứng từ mảng match. Ta cập nhật liên tục giá trị min và max. Do R - L <= 10^5, độ phức tạp này hoàn toàn chấp nhận được.

Cách Tối ưu hóa nhập xuất (C++ Fast I/O)

#include <bits/stdc++.h>
using namespace std;

int a[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
long f(long x) {
    long res = 0;
    while (x) {
        res += a[x % 10];
        x /= 10;
    }
    return res;
}
long t, l, r;
int main() {
    cin >> t;
    while (t--) {
        cin >> l >> r;
        long maxn = LONG_MIN;
        long minn = LONG_MAX;
        for (long i = l; i <= r; i++) {
            maxn = max(maxn, f(i));
            minn = min(minn, f(i));
        }
        cout << minn << " " << maxn << "\n";
    }
}

• Time Complexity: Giống Approach 1.
• Space Complexity: O(1)

Cấu trúc code tương tự Approach 1, nhưng có vẻ thiếu các tối ưu hóa nhập xuất chuẩn (ios::sync_with_stdio(false); cin.tie(nullptr);). Logic tính toán vẫn là duyệt tuần tự. Đây là cách tiếp cận cơ bản nhất về mặt logic nhưng có thể chậm hơn một chút trong môi trường Online Judge nếu không có tối ưu hóa I/O.

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

Bài học kinh nghiệm

• Ràng buộc R - L <= 10^5 là manh mối quan trọng nhất, biến bài toán từ tìm kiếm phức tạp thành bài toán duyệt đơn giản (Linear Scan).
• Biểu diễn que diêm cho các chữ số 0-9 là cố định, nên việc tính tổng que diêm cho một số chỉ cần truy cập mảng và lặp qua các chữ số.
• Nếu R - L nhỏ, việc kiểm tra từng số là đủ nhanh; không cần các thuật toán phức tạp như quy hoạch động hay toán học.

Lỗi thường gặp

• Sử dụng int để lưu biến vòng lặp i khi L và R có thể lên tới 10^18. Phải dùng long long cho biến lặp.
• Quên xử lý trường hợp số 0 (nếu L có thể là 0). Tuy nhiên đề bài nói 1 <= l, nên trường hợp này không xảy ra, nhưng logic hàm countMatch vẫn nên xử lý 0 cho chắc chắn.
• Thiếu các dòng tối ưu nhập xuất trong C++ (Fast I/O) có thể gây trễ giờ nếu số lượng test case lớn (T ~ 1000) và lượng dữ liệu vào ra lớn.