Hiểu bài toán

Bài toán yêu cầu xác định ngày và tháng tương ứng với số thứ tự n trong năm y. Năm y nằm trong khoảng từ 1900 đến 2050, và n nằm trong khoảng từ 1 đến 365. Năm có thể là năm nhuận (nếu chia hết cho 4 và không chia hết cho 100, hoặc chia hết cho 400), trong đó tháng 2 có 29 ngày thay vì 28. Mùng 1 tháng 1 là ngày thứ 1.

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

Cách Duyệt theo từng tháng (Iterative Subtraction)

#include <stdio.h>
#include <stdbool.h>

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

int main() {
    int n, y;
    scanf("%d %d", &n, &y);

    int daysInMonth[13] = {0,
        31, 28, 31, 30, 31, 30,
        31, 31, 30, 31, 30, 31
    };

    if (isLeap(y)) {
        daysInMonth[2] = 29;
    }

    int m = 1;
    while (n > daysInMonth[m]) {
        n -= daysInMonth[m];
        m++;
    }

    int d = n;
    printf("%d %d\n", d, m);

    return 0;
}

• Time Complexity: O(1) (vì số tháng là hằng số 12)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng một mảng chứa số ngày của từng tháng. Ban đầu, ta kiểm tra năm y có phải là năm nhuận không để cập nhật số ngày của tháng 2. Sau đó, ta dùng vòng lặp để trừ đi số ngày của từng tháng (bắt đầu từ tháng 1) cho đến khi số ngày còn lại n nhỏ hơn hoặc bằng số ngày của tháng hiện tại. Khi đó, n chính là ngày trong tháng đó, và biến đếm tháng chính là tháng cần tìm.

Cách Mảng cộng dồn (Prefix Sum)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int nhuan(int n){
    if (n%400==0 || (n%4==0 && n%100!=0)) return 1;
    else return 0;
}
int main(){
    int n,y;
    scanf("%d%d",&n,&y);
    int a[13];
    a[0]=0;
    for (int i=0;i<=12;i++){
        if (i==1 ||i==3||i==5||i==7||i==8||i==10||i==12) a[i]=31;
        else if (i==4||i==6||i==9||i==11) a[i]=30;
        else{
            if (nhuan(y)) a[i]=29;
            else a[i]=28;
        }
    }
    int b[13];
    b[0]=0;
    for (int i=1;i<=12;i++){
        b[i]=b[i-1]+a[i];
    }
    for (int i=0;i<=11;i++){
        if (n>b[i] && n<b[i+1]){
            printf("%d %d",n-b[i],i+1);
            return 0;
        }
    }
}

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

Phương pháp này tạo một mảng a chứa số ngày của từng tháng và một mảng b là mảng cộng dồn (prefix sum), trong đó b[i] là tổng số ngày từ đầu năm đến hết tháng i. Vòng lặp duyệt qua các tháng để tìm chỉ số i sao cho n lớn hơn tổng số ngày trước đó (b[i]) và nhỏ hơn tổng số ngày đến hết tháng hiện tại (b[i+1]). Ngày trong tháng sẽ là n - b[i] và tháng là i + 1.

Cách Đơn giản hóa Logic (Simplified Logic)

#include <stdio.h>

int main() {
    int n, y;
    scanf("%d%d", &n, &y);

    int isLeap = (y % 400 == 0) || (y % 4 == 0 && y % 100 != 0);

    int m = 1;
    int days;

    while (1) {
        if (m == 2) {
            days = isLeap ? 29 : 28;
        } else if (m == 4 || m == 6 || m == 9 || m == 11) {
            days = 30;
        } else {
            days = 31;
        }

        if (n <= days) {
            break;
        }
        n -= days;
        m++;
    }

    printf("%d %d", n, m);
    return 0;
}

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

Đây là biến thể của phương pháp duyệt, nhưng không sử dụng mảng. Số ngày của tháng được tính toán trực tiếp bên trong vòng lặp dựa trên số thứ tự tháng (m) và trạng thái năm nhuận. Nếu n nhỏ hơn hoặc bằng số ngày của tháng hiện tại, vòng lặp dừng lại và in ra kết quả. Ngược lại, trừ n đi số ngày của tháng đó và tăng tháng lên 1.

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

Bài học kinh nghiệm

• Kiểm tra năm nhuận là bước quan trọng đầu tiên để xác định số ngày của tháng 2.
• Vấn đề có thể được giải quyết bằng cách mô phỏng quá trình đi qua từng tháng trong năm và trừ đi số ngày tương ứng.

Lỗi thường gặp

• Quên cập nhật số ngày tháng 2 cho năm nhuận.
• Lỗi logic trong điều kiện năm nhuận (cần ưu tiên chia hết cho 400).
• Lỗi chỉ số mảng (nên bắt đầu từ tháng 1 hoặc sử dụng mảng có kích thước 13 phần tử với phần tử 0 là 0).