Số ngày trong tháng

Nguồn: Hỏi đáp trên nhóm học lập trình Độ khó: Dễ Tư duy Mảng Năm nhuận

Đề bài

Cho tháng và năm. Hỏi tháng đó, năm đó có bao nhiêu ngày, biết cứ mỗi 4 năm thì có một năm nhuận, nhưng mỗi 400 năm thì chỉ 97 năm nhuận vì năm thứ 100, 200 và 300 không tính là nhuận.

Input: Hai số nguyên dương lần lượt là tháng và năm hợp lệ.

Output: Một số trong đoạn $[1, 31]$ là số ngày tương ứng trong tháng, năm đó.

Ghi chú: Cấm dùng define, include, using, for, while, switch, if, break, go to, "?", ":". Code mẫu có sẵn một dòng: #include <iostream>.

Input 1

2 2454

Output 1

28

Input 2

2 6720

Output 2

29

Input 3

12 200

Output 3

31

Input 4

1 2014

Output 4

31

Lời mở đầu

Nay mình đi comment dạo thấy bài này thú vị nè 😄: một bạn hỏi xin hướng giải và "thuật toán tối ưu" cho bài này. Bài thì rất cơ bản, cái hay nằm ở chỗ đề cấm gần hết các câu lệnh điều khiển. Mình viết lại phần hướng giải đã comment (soạn trên điện thoại, hết lòng vì anh em luôn đó 😅) thành bài cho anh em nào cần tham khảo nha.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ. Các tháng 1, 3, 5, 7, 8, 10, 12 có 31 ngày; tháng 4, 6, 9, 11 có 30 ngày; riêng tháng 2 có 29 ngày nếu là năm nhuận, 28 ngày nếu không. Một năm là năm nhuận khi nó thoả 1 trong 2 trường hợp sau:

• Trường hợp 1: năm chia hết cho 4 và không chia hết cho 100.
• Trường hợp 2: năm chia hết cho 400.

Đó chính là ý "mỗi 400 năm chỉ có 97 năm nhuận" của đề: trong 400 năm có 100 năm chia hết cho 4, bỏ đi các năm thứ 100, 200, 300 (chia hết cho 100 mà không chia hết cho 400) thì còn 97. Áp vào ví dụ:

• 2 2454: 2454 không chia hết cho 4 ⇒ không nhuận ⇒ tháng 2 có 28 ngày.
• 2 6720: 6720 chia hết cho 4 và không chia hết cho 100 ⇒ năm nhuận ⇒ tháng 2 có 29 ngày.
• 12 200: tháng 12 luôn có 31 ngày (năm 200 có nhuận hay không cũng chẳng ảnh hưởng; mà 200 chia hết cho 100 nhưng không chia hết cho 400 nên cũng không nhuận).
• 1 2014: tháng 1 luôn có 31 ngày.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Làm bình thường với if / else · vi phạm ràng buộcCách 2Mảng số ngày + cộng giá trị của điều kiện · O(1)

Cách 1Làm bình thường với if / else – O(1)

Nếu không có phần "Ghi chú" thì bài này ai cũng làm được: xét tháng 2 riêng (kiểm tra năm nhuận), xét nhóm tháng 30 ngày, còn lại là 31 ngày. Mình để code ở đây để các bạn mới học dễ so sánh với cách 2, và cũng để làm "code đối chứng" khi kiểm thử:

#include <iostream>
using namespace std;

int main()
{
    int m, y;
    cin >> m >> y;
    if (m == 2)
    {
        if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)
            cout << 29;
        else
            cout << 28;
    }
    else if (m == 4 || m == 6 || m == 9 || m == 11)
        cout << 30;
    else
        cout << 31;
    return 0;
}

m, y = map(int, input().split())
if m == 2:
    if (y % 4 == 0 and y % 100 != 0) or y % 400 == 0:
        print(29)
    else:
        print(28)
elif m in (4, 6, 9, 11):
    print(30)
else:
    print(31)

Code này không nộp được

Code trên dùng if, else, using... đều nằm trong danh sách cấm của đề. Nên ta phải nghĩ cách khác.

Cách 2Mảng số ngày + cộng thẳng giá trị của điều kiện – O(1)

Nếu với những ràng buộc không cho dùng if else, switch case, toán tử 3 ngôi, các câu lệnh lặp thì rõ ràng thấy rằng mục đích của người ra đề là muốn chúng ta có thể trực tiếp đưa ra đáp án mà không cần phải xét điều kiện gì cả. Nếu đã nhìn ra điều đó thì ta có thể hình dung ngay ra được giải pháp thôi. Đặt câu hỏi: làm sao để trực tiếp đưa ra được đáp án ngay lập tức mà không cần xét điều kiện? Rất dễ để nhìn ra được như sau:

Bước 1: tra mảng. Ta tạo mảng a có 12 phần tử với các giá trị mặc định sẵn tương ứng giá trị số ngày của 12 tháng, cụ thể:

int a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

Như thế khi ta có giá trị tháng m cần tìm số ngày thì chỉ đơn giản truy xuất đến a[m-1] là ngay lập tức lấy ra được số ngày tương ứng của tháng m thôi. Phải nhớ lấy m-1 chứ không lấy m nhé, vì index mảng tính bắt đầu từ 0. Bạn nào không thích thì tạo mảng có 13 phần tử, coi như bỏ qua index 0 (cho nó đại số gì đó, vd: 0 chẳng hạn), lúc này gọi a[m] thì ok.

Bước 2: tháng 2 năm nhuận. Tuy nhiên riêng tháng 2 nó lại tuỳ thuộc ràng buộc: nếu năm nhuận thì có 29 ngày, năm không nhuận thì có 28 ngày. Vậy nên trong tình huống này ta hãy cứ đưa ra việc xét điều kiện, nhưng không đặt nó trong câu lệnh điều kiện hay lặp gì cả mà cứ đơn thuần xét nó thôi, máy tính sẽ trả về true hay false với điều kiện đó. Trong ngôn ngữ C/C++ thì true đại diện là số 1 còn false đại diện là số 0. Chính vì thế:

• Chỗ tháng 2 ta cứ cho sẵn nó 28 ngày, rồi lấy kết quả 28 ngày đó cộng thêm giá trị có được từ việc xét điều kiện. Nếu điều kiện thoả thì $28 + 1 = 29$; nếu không thoả thì $28 + 0$ vẫn là 28.
• Còn với các tháng khác có 30 hay 31 ngày thì vì điều kiện có kèm m == 2 nên sẽ luôn là false (0), cộng thêm 0 sẽ không bị thay đổi giá trị.

Công thức

a[m - 1] + (m == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0))
Phần trong ngoặc là một biểu thức logic, giá trị của nó (0 hoặc 1) được cộng thẳng vào số ngày tra từ mảng.

Các bạn nhập tháng, năm vào khung dưới đây rồi bấm Tiếp để xem biểu thức được tính ra sao nhé:

Tháng m Năm y

Ví dụ nhanh:

Code nhanh của mình để anh em tham khảo để hiểu rõ tư tưởng mình nói ở trên nè (dòng #include <iostream> là dòng code mẫu có sẵn; không dùng using nên phải ghi std::cin, std::cout):

#include <iostream>
int main() {
    int a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int m, y;
    std::cin >> m >> y;
    std::cout << a[m - 1] + (m == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0));
    return 0;
}

a = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
m, y = map(int, input().split())
print(a[m - 1] + (m == 2 and ((y % 4 == 0 and y % 100 != 0) or y % 400 == 0)))

Bản Python

Python cũng làm y hệt: m == 2 and (...) trả về False hoặc giá trị True/False của phần sau, mà trong Python True cộng với số nguyên thì được tính là 1, False là 0.

Lưu ý nhỏ về dấu ":" trong std::

Đề cấm "?" và ":" là để chặn toán tử 3 ngôi ? :. Nhưng nếu hệ thống chấm quét cứng từng ký tự : trong code thì std::cin cũng sẽ bị dính. Khi đó các bạn có thể đổi sang scanf/printf (với trình biên dịch GCC, thư viện <iostream> đã kéo theo khai báo của 2 hàm này), phần tính toán giữ nguyên:

#include <iostream>
int main() {
    int a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int m, y;
    scanf("%d%d", &m, &y);
    printf("%d", a[m - 1] + (m == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)));
    return 0;
}

Khung chạy tay dưới đây chạy đúng từng dòng code C++ của mình ở trên, dòng 6 mình tách ra thành nhiều bước nhỏ để các bạn thấy từng phần của biểu thức được tính như thế nào:

C++▶ Chạy tay từng dòng codeTra mảng a[m − 1] rồi cộng thêm giá trị 0/1 của điều kiện tháng 2 năm nhuận.

Dữ liệu vào (stdin) – sửa thoải mái2 6720

Dữ liệu mẫu:

1#include <iostream>

2int main() {

3 int a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

4 int m, y;

5 std::cin >> m >> y;

6 std::cout << a[m - 1] + (m == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0));

7 return 0;

8}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: 1 mảng 12 phần tử cố định: $O(1)$.
• Thời gian: 1 lần truy xuất mảng và vài phép chia lấy dư: $O(1)$.

Không gian$O(1)$

Thời gian$O(1)$

Bài học rút ra: một biểu thức logic cũng là một con số (0 hoặc 1), và khi đề bài cấm các câu lệnh điều khiển thì hãy nghĩ cách "tính thẳng" ra đáp án bằng mảng tra cứu và các biểu thức như vậy 😃.

Ghi chú của mình: code C++ và Python của cả 2 cách (và bản scanf/printf trong khung lưu ý) đã được kiểm tra với 4 test của đề, toàn bộ 12 tháng của các năm đặc biệt (1, 4, 100, 200, 300, 400, 1900, 2000, 2023, 2024) và 250 bộ tháng/năm ngẫu nhiên (năm tới $10^9$), so với thư viện calendar của Python và quy tắc năm nhuận – khớp hết. Mình cũng quét code của cách 2: không chứa từ khoá nào bị cấm, chỉ có dấu : trong std:: như đã lưu ý ở trên.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇