HSPC14F - Giải thưởng
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một trường Công Nghệ trao tiền thưởng cho học sinh đi học đầy đủ và đúng giờ. Nếu vắng mặt trong ba ngày liên tiếp hoặc đi muộn nhiều hơn một lần thì sinh viên sẽ bị tịch thu tiền thưởng. Trong suốt khoảng thời gian N ngày, “bản điểm danh” của một học sinh là một chuỗi N ký tự L (muộn), O (đúng giờ), và A (vắng mặt). Mặc dù có 81 chuỗi trong suốt 4 ngày có thể được tạo ra, chính xác 43 chuỗi sẽ dẫn đến giải thưở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 Hỏi có bao nhiêu chuỗi "giải thưởng" tồn tại sau một khoảng thời gian N ngày?
Một trường Công Nghệ trao tiền thưởng cho học sinh đi học đầy đủ và đúng giờ. Nếu vắng mặt trong ba ngày liên tiếp hoặc đi muộn nhiều hơn một lần thì sinh viên sẽ bị tịch thu tiền thưởng. Trong suốt khoảng thời gian N ngày, “bản điểm danh” của một học sinh là một chuỗi N ký tự L (muộn), O (đúng giờ), và A (vắng mặt). Mặc dù có 81 chuỗi trong suốt 4 ngày có thể được tạo ra, chính xác 43 chuỗi sẽ dẫn đến giải thưở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
Hỏi có bao nhiêu chuỗi "giải thưởng" tồn tại sau một khoảng thời gian N ngày?.
Input
Gồm nhiều test, mỗi test nằm trên một dòng gồm 1 số nguyên N ≤ 3000
Output
Với mỗi test, in ra trên một dòng kết quả phải tính
Example
Input: 4 Output: 43
- Người up: beo_chay_so
- Nguồn bài: HSPC 2014