Giải thưởng

Điểm: 1,10 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

HSPC 2014

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một trường Công Nghệ trao tiền thưởng cho học sinh đi học đầy đủ và đúng giờ. Nếu vắng mặt trong ba ngày liên tiếp hoặc đi muộn nhiều hơn một lần thì sinh viên sẽ bị tịch thu tiền thưởng. Trong suốt khoảng thời gian ~N~ ngày, "bản điểm danh" của một học sinh là một chuỗi ~N~ ký tự ~L~ (muộn), ~O~ (đúng giờ), và ~A~ (vắng mặt). Mặc dù có ~81~ chuỗi trong suốt ~4~ ngày có thể được tạo ra, chính xác ~43~ chuỗi sẽ dẫn đến giải thưởng:

~OOOO \ OOOA \ OOOL \ OOAO \ OOAA \ OOAL \ OOLO \ OOLA \ OAOO \ OAOA \ OAOL \ OAAO \ OAAL \ OALO \ OALA \ OLOO \ OLOA~

~OLAO \ OLAA \ AOOO \ AOOA \ AOOL \ AOAO \ AOAA \ AOAL \ AOLO \ AOLA \ AAOO \ AAOA \ AAOL \ AALO \ AALA \ ALOO \ ALOA~

~ALAO \ ALAA \ LOOO \ LOOA \ LOAO \ LOAA \ LAOO \ LAOA \ LAAO~

Hỏi có bao nhiêu chuỗi "giải thưởng" tồn tại sau một khoảng thời gian ~N~ ngày?.

Input

Gồm nhiều test, mỗi test nằm trên một dòng gồm ~1~ số nguyên ~N \leq 3000~.

Output

Với mỗi test, in ra trên một dòng kết quả phải tính.

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

dragon3012009 đã bình luận lúc 4, Tháng 5, 2025, 16:35 ← sửa 2 →

Mình thấy khá ít bạn làm bài này nên mình có một solution như sau

Bài này sử dụng Đệ quy có nhớ và Bignum

Ta thấy có 3 trạng thái ngày học - số ngày sủi - đi học muộn chưa nên ta có mảng dp[pos][4][2]

Ta dễ dàng tìm được công thức chuyển trạng thái cơ bản của đệ quy có nhớ

Chú ý nho nhỏ là trong input là nhiều test case chứ không phải một test và các bạn có thể nhận ra không cần memset mảng dp vì nó có tính chất như nhau

Code tham khảo

Cho mình xin một upvote nha ○( ＾皿＾)っ Hehehe…

0

nguentapcode đã bình luận lúc 5, Tháng 9, 2024, 8:59

cho xin ý tưởng bài này với