COUNTPL - Đếm số Palindrome
Giới hạn- Thời gian: 0.1s
- 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.
Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:
‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’
‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’
‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’
Yêu cầu
Cho xâu ký tự s, cần tìm cách biểu diễn xâu s dưới dạng một dãy gồm số ít nhất các palindrome. Ví dụ: Cho s=‘bobseesanna’, do ta có ‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’ và không thể biểu diễn ‘bobseesanna’ bởi ít hơn là 3 palindrome nên biểu diễn này chính là biểu diễn cần tìm.
Input
Gồm một dòng chứa xâu ký tự s gồm không quá 255 ký tự.
Output
Gồm một dòng duy nhất ghi k là số lượng ít nhất các palindrome trong biểu diễn tìm được.
Example
Input:
bobseesanna
Output:
3
- Người up: tohuuquan
- Nguồn bài: Cổ điển