Editorial for Lịch Của Sên


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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:

  1. la_nam_nhuan(y): năm \(y\) có nhuận không?
  2. so_ngay_cua_thang(m, y): tháng \(m\) của năm \(y\) có bao nhiêu ngày?
  3. 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

There are no comments at the moment.