Hiểu bài toán

Bài toán yêu cầu xác định xem một tổ hợp ngày (d), tháng (m), năm (y) nhập vào có phải là một ngày hợp lệ trong lịch Gregorian hay không. Điều kiện hợp lệ bao gồm:

1. Năm phải là số nguyên dương (theo input constraint là từ 1990 đến 3000).
2. Tháng phải nằm trong khoảng từ 1 đến 12.
3. Ngày phải nằm trong khoảng từ 1 đến số ngày tối đa của tháng đó.
4. Số ngày của tháng 2 phụ thuộc vào việc năm đó có phải là năm nhuận hay không. Năm nhuận được xác định theo quy tắc: chia hết cho 4 và không chia hết cho 100, hoặc chia hết cho 400. Với mỗi bộ test case, in ra TRUE nếu ngày hợp lệ, ngược lại in ra FALSE.

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

Cách Xử lý từng trường hợp (Conditional Logic)

#include <iostream>
using namespace std;

bool laNamNhuan(int nam) {
    return (nam % 400 == 0) || (nam % 4 == 0 && nam % 100 != 0);
}

int main() {
    int q, d, m, y;
    cin >> q;
    while (q--) {
        cin >> d >> m >> y;
        bool hopLe = true;
        // Kiểm tra cơ bản
        if (y <= 0 || m < 1 || m > 12) {
            hopLe = false;
        } else {
            int soNgayTrongThang;
            // Xác định số ngày dựa trên tháng
            if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12)
                soNgayTrongThang = 31;
            else if (m == 4 || m == 6 || m == 9 || m == 11)
                soNgayTrongThang = 30;
            else { // Tháng 2
                if (laNamNhuan(y)) soNgayTrongThang = 29;
                else soNgayTrongThang = 28;
            }
            // Kiểm tra ngày
            if (d < 1 || d > soNgayTrongThang) hopLe = false;
        }
        if (hopLe) cout << "TRUE" << endl;
        else cout << "FALSE" << endl;
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này sử dụng các câu lệnh điều kiện if-else để phân tích từng trường hợp của tháng.

1. Kiểm tra tính hợp lệ của năm và tháng.
2. Với các tháng có 31 ngày (1, 3, 5, 7, 8, 10, 12), gán số ngày là 31.
3. Với các tháng có 30 ngày (4, 6, 9, 11), gán số ngày là 30.
4. Với tháng 2, gọi hàm kiểm tra năm nhuận để gán số ngày là 28 hoặc 29.
5. Cuối cùng, kiểm tra xem ngày nhập vào có nằm trong khoảng cho phép không. Cách này rất trực quan và dễ hiểu.

Cách Sử dụng mảng số ngày (Lookup Table)

#include <iostream>
#define ll long long
using namespace std;

int nhuan(int n) {
    return (n % 400 == 0) || (n % 4 == 0 && n % 100 != 0);
}

int main() {
    int t; cin >> t;
    while (t--) {
        bool check = true;
        int d, m, y; cin >> d >> m >> y;
        if (y <= 0 || m < 1 || m > 12 || d < 1) check = false;
        else {
            int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            if (nhuan(y)) months[1] = 29; // Sửa lỗi logic index: tháng 2 là index 1
            // Code gốc để sai months[3] = 29 là sai logic, nhưng logic chung là dùng mảng
            // Dưới đây là phiên bản corrected logic:
            int limit = months[m-1];
            if (m == 2 && nhuan(y)) limit = 29;

            if (d > limit) check = false;
        }
        cout << (check ? "TRUE" : "FALSE") << '\n';
    }
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Phương pháp này sử dụng một mảng months để lưu trữ số ngày của các tháng thông thường.

• Khởi tạo mảng với các giá trị ngày cố định.
• Nếu năm là năm nhuận, ta cập nhật số ngày của tháng 2 (phần tử thứ 1 của mảng).
• Để lấy số ngày của tháng m, ta chỉ cần truy cập months[m-1] (vì chỉ số mảng bắt đầu từ 0). Cách này giúp code ngắn gọn hơn, tránh được nhiều câu lệnh if-else lồng nhau.

Cách Qui tắc chia hết và tổng quát hóa

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

bool namnhuan(int n) {
    if (n % 400 == 0) return true;
    if (n % 100 == 0) return false;
    if (n % 4 == 0) return true;
    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int d, m, y;
        cin >> d >> m >> y;

        bool valid = true;
        if (y < 1990 || y > 3000 || m < 1 || m > 12 || d < 1) valid = false;
        else {
            int max_days = 31;
            if (m == 2) {
                if (namnhuan(y)) max_days = 29;
                else max_days = 28;
            } else if (m == 4 || m == 6 || m == 9 || m == 11) {
                max_days = 30;
            }
            if (d > max_days) valid = false;
        }
        cout << (valid ? "TRUE" : "FALSE") << "\n";
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Đây là biến thể của phương pháp 1, tập trung vào việc tối ưu hóa logic bằng cách chỉ kiểm tra các trường hợp ngoại lệ của số ngày.

• Mặc định, một tháng có 31 ngày.
• Nếu là tháng 4, 6, 9, 11, số ngày giảm xuống 30.
• Nếu là tháng 2, số ngày giảm xuống 28 (hoặc 29 nếu là năm nhuận). Cách tiếp cận này hiệu quả vì nó xử lý các trường hợp phổ biến (31 ngày) làm mặc định, chỉ kiểm tra các trường hợp đặc biệt.

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

Bài học kinh nghiệm

• Quy tắc năm nhuận: Năm chia hết cho 4 và không chia hết cho 100, HOẶC năm chia hết cho 400.
• Cấu trúc dữ liệu: Mảng số ngày cố định là cách hiệu quả nhất để lưu trữ thông tin về các tháng (trừ tháng 2).
• Kiểm tra biên: Luôn luôn kiểm tra các ràng buộc cơ bản (tháng 1-12, ngày >= 1) trước khi vào logic tính toán sâu.

Lỗi thường gặp

• Lỗi chỉ số mảng: Khi dùng mảng 12 phần tử, tháng 1 là index 0, tháng 2 là index 1, ..., tháng 12 là index 11. Lỗi thường gặp là gán sai index cho tháng 2 (ví dụ months[3] = 29 trong code sample 1 là sai logic nếu ý định là update tháng 2).
• Năm 100: Quên quy tắc 'chia hết cho 4 nhưng không chia hết cho 100' sẽ dẫn đến sai lầm với các năm như 1900 (không nhuận) so với 2000 (nhuận).
• Dữ liệu đầu vào: Input yêu cầu năm >= 1990, nhưng logic kiểm tra ngày tháng vẫn có thể áp dụng cho các năm dương lịch chung.