Đề bài
Một câu lạc bộ họp vào ngày đầu tiên của mỗi tháng, và buổi họp nào rơi vào Chủ nhật thì được ăn bữa sáng muộn. Hãy đếm số tháng, từ tháng Một năm start_year đến tháng Mười hai năm end_year, có ngày mùng 1 là Chủ nhật, theo lịch Gregory. Mốc để tính: ngày 1 tháng 1 năm 2023 là Chủ nhật. Nhớ quy tắc năm nhuận: chia hết cho 4, trừ các năm tròn thế kỷ thì phải chia hết cho 400.
Hãy viết counting_sundays(start_year, end_year).
Đầu vào
start_year: Năm đầu tiên, tính từ tháng Một.
end_year: Năm cuối cùng, tính hết tháng Mười hai.
Đầu ra
Trả về số tháng trong khoảng đó có ngày mùng 1 là Chủ nhật.
Ràng buộc
1600 ≤ start_year ≤ end_year ≤ 2400
Ví dụ
Đầu vào:
start_year = 2023
end_year = 2023
Kết quả mong đợi:
expected = 2
Đầu vào:
long long start_year = 2023;
long long end_year = 2023;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long start_year = 2023;
long end_year = 2023;
Kết quả mong đợi:
long expected = 2;
Giải thích
Năm 2023 chỉ có tháng Một và tháng Mười bắt đầu vào Chủ nhật, nên đáp án là 2.
Đầu vào:
start_year = 2024
end_year = 2025
Kết quả mong đợi:
expected = 3
Đầu vào:
long long start_year = 2024;
long long end_year = 2025;
Kết quả mong đợi:
long long expected = 3;
Đầu vào:
long start_year = 2024;
long end_year = 2025;
Kết quả mong đợi:
long expected = 3;
Giải thích
Năm 2024 có tháng Chín và tháng Mười hai, năm 2025 có tháng Sáu: 3 tháng.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tìm thứ của ngày 1 tháng 1 năm bắt đầu từ một ngày đã biết, hoặc dùng công thức tính thứ.
Gợi ý 2
Sang tháng tiếp theo, thứ trong tuần dịch đi bằng số ngày của tháng đó chia lấy dư cho 7.
Gợi ý 3
Tháng Hai có 29 ngày trong năm nhuận: chia hết cho 4, nhưng năm tròn thế kỷ thì chỉ khi chia hết cho 400.
Độ phức tạp mong đợi
thời gian O(years), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.