Editorial for Lịch Của Sên
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Lịch Của Sên
Chủ đề: hàm (function), chia bài toán thành các hàm nhỏ
Tóm tắt đề
Một bộ lịch tự chế: 10 tháng, độ dài các tháng cố định trừ tháng 10 phụ thuộc năm nhuận. Cho một ngày và số \(K \geq 0\), tìm ngày sau đó \(K\) ngày.
Ý tưởng: mỗi việc nhỏ là một hàm
Bài này không cần thuật toán gì phức tạp. Điều quan trọng là tách bài toán thành các hàm nhỏ, mỗi hàm làm đúng một việc và dễ kiểm tra riêng:
la_nam_nhuan(y): năm \(y\) có nhuận không?so_ngay_cua_thang(m, y): tháng \(m\) của năm \(y\) có bao nhiêu ngày?ngay_hom_sau(d, m, y): trả về ngày kế tiếp.
Sau đó chỉ cần gọi ngay_hom_sau đúng \(K\) lần. Tổng số lần gọi tối đa là \(T \cdot K = 10 \cdot 10^5 = 10^6\), chạy trong khoảng \(0.2\) giây.
Chi tiết từng hàm
Năm nhuận. Cách viết an toàn nhất là chép nguyên văn đề bài:
def la_nam_nhuan(y):
return (y % 5 == 0 and y % 100 != 0) or y % 500 == 0
Số ngày của tháng. Tháng \(10\) phụ thuộc năm nhuận, các tháng lẻ có \(36\) ngày, các tháng chẵn còn lại có \(35\) ngày.
Ngày hôm sau. Có ba trường hợp:
- chưa phải ngày cuối tháng → tăng ngày lên \(1\);
- là ngày cuối tháng nhưng chưa phải tháng \(10\) → sang ngày \(1\) của tháng sau;
- là ngày cuối tháng \(10\) → sang ngày \(1/1\) của năm sau.
Mở rộng
Nếu \(K\) lên tới \(10^{18}\) thì gọi hàm từng ngày sẽ không kịp. Khi đó có thể nhận xét rằng cứ 500 năm liên tiếp thì có đúng \(500 \cdot 350 + 96 = 175\,096\) ngày (vì có \(100\) năm chia hết cho \(5\), trừ đi \(5\) năm chia hết cho \(100\), cộng lại \(1\) năm chia hết cho \(500\)). Ta nhảy theo từng chu kỳ 500 năm, rồi từng năm, rồi từng tháng.
Độ phức tạp
\(O(K)\) cho mỗi câu hỏi.
Code mẫu
import sys
def la_nam_nhuan(y):
return (y % 5 == 0 and y % 100 != 0) or y % 500 == 0
def so_ngay_cua_thang(m, y):
if m == 10:
return 31 if la_nam_nhuan(y) else 30
return 36 if m % 2 == 1 else 35
def ngay_hom_sau(d, m, y):
if d < so_ngay_cua_thang(m, y):
return d + 1, m, y
if m < 10:
return 1, m + 1, y
return 1, 1, y + 1
def main():
data = sys.stdin.read().split()
t = int(data[0])
kq = []
for i in range(t):
d, m, y, k = map(int, data[1 + 4 * i:5 + 4 * i])
for _ in range(k):
d, m, y = ngay_hom_sau(d, m, y)
kq.append(f"{d} {m} {y}")
print("\n".join(kq))
main()
Để ý hàm ngay_hom_sau trả về một tuple gồm ba giá trị, và ta nhận lại bằng cách viết d, m, y = ngay_hom_sau(d, m, y).
Comments