Ghép chữ
Đề bài
Mô tả
Vài năm trước, giáo sư H trở thành nhà vô địch Siêu cúp Olympic Tin học dành cho học sinh Việt Nam hai lần liên tiếp! Là người đầu tiên đạt được chiến tích vang dội như vậy, giáo sư nhanh chóng trở thành một ngôi sao sáng của làng giải trí. Một trong những người hâm mộ trung thành nhất của giáo sư H, anh Qu, đã tặng giáo sư một món quà kỳ lạ, đó là... một xâu .
Vì thử thách tiếp theo của giáo sư H là Chung kết thế giới ICPC thường niên, giáo sư nghĩ ra bài toán sau: giả sử tôi muốn chọn bốn ký tự khác nhau trong xâu sao cho không có hai ký tự liên tiếp nào cùng được chọn, và ghép các ký tự này lại theo đúng thứ tự ban đầu thì được từ ICPC. Có bao nhiêu cách làm như vậy?
Một cách hình thức, đánh số các ký tự của xâu từ đến . Hãy đếm số bộ chỉ số thỏa mãn:
- ;
- ;
- các ký tự thứ , , và của lần lượt là I, C, P và C.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test là một dòng chứa xâu . Xâu chỉ gồm các chữ cái tiếng Anh in hoa, độ dài từ đến .
Dữ liệu vào kết thúc bằng một dòng chỉ chứa một ký tự $, dòng này không phải là một bộ test.
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng một số nguyên là số bộ chỉ số thỏa mãn yêu cầu.
Ràng buộc
- , chỉ gồm chữ cái tiếng Anh in hoa.
- Tổng độ dài các xâu trong dữ liệu vào không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| IICCPPCC INTERNATIONALCOLLIGIATEPROGRAMMINGCONTEST GOODLUCKHAVEFUN ENJOYYOURTIMEATHCMUTEANDHAPPYCODDING WISHYOUMANYACCEPTEDCODE RIGIONALICPCRIGIONALICPCRIGIONALICPC $ |
5 2 0 2 2 10 |
Ở bộ test đầu tiên có năm bộ thỏa mãn: , , , và . |
| I ICPC IXCXPXC $ |
0 0 1 |
Xâu ICPC không có cách chọn nào vì bốn ký tự đứng liền nhau; trong xâu IXCXPXC chỉ có bộ . |
Bình luận