Hiểu bài toán

Một chiếc đồng hồ LED hiển thị giờ và phút (từ 00:00 đến 23:59). Mỗi chữ số (0-9) tiêu tốn một số lượng vạch LED nhất định để hiển thị. Ví dụ: chữ số '1' dùng 2 vạch, chữ số '8' dùng 7 vạch. Cho trước tổng số vạch LED $n$ mà người dùng đếm được, nhiệm vụ là tìm một thời điểm (giờ và phút) sao cho tổng số vạch LED của 4 chữ số hiển thị (giờ chục, giờ đơn, phút chục, phút đơn) bằng $n$. Nếu có nhiều đáp án, in ra bất kỳ. Nếu không có, in ra 'Impossible'. Dải giờ hợp lệ: $0 \le h \le 24$, $0 \le m \le 60$.

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 main() {
    int n; 
    cin >> n;

    // Mảng lưu số vạch LED cho các chữ số từ 0 đến 9
    int led[10] = {6,2,5,5,4,5,6,3,7,6};

    // Duyệt qua tất cả các mốc thời gian có thể
    for (int h = 0; h <= 24; h++) {
        for (int m = 0; m <= 60; m++) {
            // Tính tổng số vạch LED của 4 chữ số
            int sum = 0;
            sum += led[h / 10]; // Chữ số hàng chục của giờ
            sum += led[h % 10]; // Chữ số hàng đơn vị của giờ
            sum += led[m / 10]; // Chữ số hàng chục của phút
            sum += led[m % 10]; // Chữ số hàng đơn vị của phút

            if (sum == n) {
                // In ra kết quả với định dạng 2 chữ số và thoát chương trình
                cout << setfill('0') << setw(2) << h << ":"
                     << setfill('0') << setw(2) << m;
                return 0;
            }
        }
    }

    cout << "Impossible";
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Ta tạo một mảng led chứa số vạch cho mỗi chữ số 0-9. Sau đó, ta sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các giá trị giờ (0-24) và phút (0-60). Với mỗi cặp (giờ, phút), ta tách từng chữ số, tra cứu trong mảng led, cộng lại để được tổng $S$. Nếu $S$ bằng $n$, ta in ra và kết thúc. Nếu duyệt hết mà không tìm thấy, in 'Impossible'. Do số lượng thời điểm khá nhỏ (25 * 61 ≈ 1525), phương pháp này chạy rất nhanh.

Cách Tối ưu Brute Force

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

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

int countLED(int x) {
    // Hàm đếm LED cho một số 2 chữ số (0-99)
    // Nếu x < 10, ví dụ x=5 -> hàng chục là 0, hàng đơn vị là 5
    int d1 = x / 10;
    int d2 = x % 10;
    return a[d1] + a[d2];
}

int main() {
    int n;
    cin >> n;

    for (int h = 0; h <= 24; h++) {
        for (int m = 0; m <= 60; m++) {
            // Tính tổng bằng cách gọi hàm helper
            if (countLED(h) + countLED(m) == n) {
                cout << setfill('0') << setw(2) << h << ":"
                     << setfill('0') << setw(2) << m;
                return 0;
            }
        }
    }

    cout << "Impossible";
    return 0;
}

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

Phương pháp này về cơ bản tương đương với Brute Force nhưng được tổ chức code gọn gàng hơn với hàm countLED(int x) để tính số vạch cho một số hai chữ số (bao gồm cả số 0 ở hàng chục nếu số đó là 0-9). Logic duyệt vẫn là lồng vòng lặp 24x60. Tính toán vẫn là O(1) do số lượng vòng lặp cố định.

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

Bài học kinh nghiệm

• Bài toán có không gian tìm kiếm rất nhỏ (chỉ 1525 thời điểm), nên giải pháp duyệt toàn bộ (Brute Force) là tối ưu và đảm bảo tìm được đáp án nếu có.
• Cần xử lý đúng định dạng in ra: giờ và phút phải được in thành 2 ký tự, tức là thêm số 0 ở phía trước nếu là số một chữ số (ví dụ: 5 phút in là '05').
• Dải giờ và phút cần lưu ý: giờ có thể là 24 (ví dụ 24:00), phút có thể là 60 (ví dụ 00:60 trong một số trường hợp hiếm, nhưng đề bài cho phép m <= 60). Tuy nhiên, theo chuẩn thời gian, phút thường chạy đến 59. Đề bài ghi 0 <= m <= 60 nên ta cần duyệt cả m=60 để an toàn.

Lỗi thường gặp

• Quên xử lý định dạng in ra (không in số 0 ở hàng chục): In '1:2' thay vì '01:02'.
• Sai lệch mảng LED: Đảm bảo mảng LED int led[10] = {6,2,5,5,4,5,6,3,7,6} là chính xác theo yêu cầu của bài toán (không phải theo chuẩn 7-segment thực tế nếu đề bài quy định khác).
• Lỗi truy cập mảng: Khi tách số, ví dụ h=5, h/10 sẽ là 0, h%10 là 5. Cần đảm bảo mảng LED có kích thước đủ và giá trị tại index 0 (số 0) là 6.