Hiểu bài toán

Bài toán yêu cầu tìm số nguyên không âm lớn nhất có thể thỏa mãn hai điều kiện:

1. Khi hiển thị số đó trên 7 thanh LED (kiểu 7-segment), tổng số thanh LED đang sáng đúng bằng N.
2. Số đó chỉ được sử dụng các chữ số có trong tập M chữ số cho trước (các chữ số phân biệt và tăng dần).

Mật mã phải là số lớn nhất có thể, nghĩa là ưu tiên số có nhiều chữ số nhất, và nếu cùng độ dài thì ưu tiên số có chữ số lớn nhất ở vị trí cao nhất.

Ràng buộc: N <= 10^5, M <= 10.

Ví dụ:

• Số 0 tốn 6 LED, số 1 tốn 2 LED, số 2 tốn 5 LED, v.v.
• Input: N=7, M=8, các chữ số {0, 2, 3, 4, 5, 6, 8, 9}. Output: 8 (vì 8 tốn 7 LED).
• Input: N=6, M=1, chữ số {0}. Output: 0 (vì 0 tốn 6 LED).
• Input: N=15, M=8, các chữ số {0, 2, 3, 4, 5, 6, 8, 9}. Output: 954 (9 tốn 6, 5 tốn 5, 4 tốn 4 => tổng 15).

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

Cách Quy hoạch động - Đếm số lượng chữ số (DP Count)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int dp[100005]; // dp[i]: số lượng chữ số tối đa để đạt tổng LED là i

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<int> digits(M);
    for(int i=0; i<M; ++i) cin >> digits[i];

    // Khởi tạo dp
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;

    // Quy hoạch động
    for (int i = 1; i <= N; ++i) {
        for (int d : digits) {
            int c = cost[d];
            if (i >= c && dp[i - c] != -1) {
                dp[i] = max(dp[i], dp[i - c] + 1);
            }
        }
    }

    // Nếu không có cách tạo ra N LED
    if (dp[N] == -1 && N == 0 && count(digits.begin(), digits.end(), 0)) {
        cout << 0 << endl;
        return 0;
    }

    int len = dp[N];
    string res = "";
    int current_sum = N;

    // Xây dựng số lớn nhất
    for (int i = 0; i < len; ++i) {
        // Sắp xếp giảm dần để thử từ chữ số lớn nhất
        sort(digits.rbegin(), digits.rend());
        for (int d : digits) {
            int c = cost[d];
            if (current_sum >= c && dp[current_sum - c] == len - i - 1) {
                // Chữ số 0 không được là số đứng đầu trừ khi số là 0
                if (i == 0 && len > 1 && d == 0) continue;
                res += (char)(d + '0');
                current_sum -= c;
                break;
            }
        }
    }

    if (res.empty()) cout << 0 << endl;
    else cout << res << endl;

    return 0;
}

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

Cách tiếp cận này chia bài toán làm 2 giai đoạn:

1. Quy hoạch động để tìm độ dài: Dùng mảng dp[i] lưu số lượng chữ số tối đa có thể tạo ra với tổng LED bằng i. Công thức: dp[i] = max(dp[i], dp[i - cost[d]] + 1) với mọi chữ số d cho phép.
2. Xây dựng số từ độ dài: Sau khi biết số lượng chữ số tối đa là len, ta lần lượt chọn từng chữ số từ cao xuống thấp (thử 9 trước, 8 sau...). Nếu chọn chữ số d, ta kiểm tra xem phần còn lại (current_sum - cost[d]) có thể tạo ra đúng len - 1 chữ số hay không bằng cách tra bảng dp. Nếu được, ta chọn d và lặp lại.

Cách này đảm bảo tìm được số lớn nhất vì ưu tiên độ dài (số chữ số) trước, sau đó ưu tiên giá trị chữ số từ trái sang phải.

Cách Quy hoạch động - Đếm số lượng (Tối ưu)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = -1e9;
int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int dp[100005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<int> digits(M);
    for(int i=0; i<M; ++i) cin >> digits[i];

    // Khởi tạo
    for (int i = 0; i <= N; ++i) dp[i] = INF;
    dp[0] = 0;

    // DP: Tìm số lượng chữ số lớn nhất
    for (int i = 0; i <= N; ++i) {
        if (dp[i] < 0) continue;
        for (int d : digits) {
            int c = cost[d];
            if (i + c <= N) {
                dp[i + c] = max(dp[i + c], dp[i] + 1);
            }
        }
    }

    int L = dp[N];
    // Xử lý trường hợp đặc biệt N=0 hoặc chỉ có số 0
    if (L <= 0) {
        if (N == 6 && find(digits.begin(), digits.end(), 0) != digits.end()) {
            cout << 0 << endl;
            return 0;
        }
    }

    // Sắp xếp digits giảm dần để ưu tiên số lớn
    sort(digits.begin(), digits.end(), greater<int>());

    string res = "";
    int current_s = N;

    // Xây dựng số
    for (int i = 0; i < L; ++i) {
        for (int d : digits) {
            int c = cost[d];
            if (current_s >= c && dp[current_s - c] == L - i - 1) {
                if (i == 0 && L > 1 && d == 0) continue;
                res += (char)(d + '0');
                current_s -= c;
                break;
            }
        }
    }

    cout << res << endl;
    return 0;
}

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

Đây là biến thể của phương pháp DP đếm số lượng. Logic cơ bản giống hệt phương pháp 1.

• Bước 1: Dùng DP để tính dp[s] là số lượng chữ số tối đa có thể tạo ra với tổng LED là s. Độ phức tạp O(N*M).
• Bước 2: Dùng dp để truy vấn dựng số lớn nhất. Ta ưu tiên thử các chữ số lớn nhất trước. Nếu chọn chữ số d, ta kiểm tra xem t tổng LED còn lại (current_s - cost[d]) có thể tạo ra đúng số lượng chữ số còn lại (L - 1) hay không.

Phương pháp này đảm bảo tính đúng đắn và hiệu quả về mặt thời gian trong giới hạn của đề bài.

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán cái túi (Knapsack) hoặc bài toán tìm cách biểu diễn số N bằng các chi phí (cost) cho trước sao cho số lượng phần tử là lớn nhất.
• Để tạo ra số lớn nhất, ta cần tối ưu hóa theo thứ tự ưu tiên: 1. Số lượng chữ số (nhiều nhất), 2. Giá trị các chữ số từ trái sang phải (lớn nhất có thể).
• Mảng dp chỉ dùng để xác nhận xem một tổng LED cụ thể có thể đạt được độ dài tối đa bao nhiêu, từ đó hỗ trợ việc chọn lọc các chữ số trong quá trình dựng số.

Lỗi thường gặp

• Quên xử lý trường hợp đặc biệt khi M=1 và chữ số đó là 0. Khi đó, nếu N khớp với cost của 0 (tức 6), đáp án là '0'. Các thuật toán dựng số thông thường sẽ từ chối số 0 đứng đầu nếu độ dài > 1.
• Nếu chỉ dùng DP để kiểm tra tồn tại mà không lưu số lượng, ta không thể phân biệt được giữa việc tạo ra số có 1 chữ số và số có nhiều chữ số (ví dụ: N=6, số 0 tốn 6 LED, số 888... nhưng 8 tốn 7 LED nên không dùng được). Do đó bắt buộc phải dùng DP tối ưu số lượng.
• Sắp xếp các chữ số cho phép trước khi DP hay trước khi dựng số là cần thiết để đảm bảo ưu tiên thử các số lớn trước, nhưng quan trọng nhất là logic "chọn chữ số lớn nhất có thể tại bước hiện tại mà vẫn đảm bảo hoàn thiện phần còn lại".