Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

COUNTPL - Đếm số Palindrome

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/countpl


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

Được gửi lên bởi:Quan To
Ngày:2010-07-30
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED VB.NET
Nguồn bài:Cổ điển

hide comments
2015-09-08 14:13:27
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-06-30 08:31:38 Bee
1 đấm AC
2015-06-08 14:09:16 Thắng Ðam Mê
Vãi thiệt, làm trên máy tính cứ ra kq sai, tự nhiên lêm ipad là làm đúng
2015-05-03 16:02:25 even when you try to hurt me...
nhìn nhầm 255 thành 225 nộp mãi ms AC :v
2015-04-16 18:01:34 Prismatic
mình làm QHĐ 2 lần :D O(n^2)
2014-10-29 14:26:01 Change The World
thật đơn giản=))
2014-09-30 15:22:21 livw
boobs see anal
2014-07-07 16:25:09 John and the cows
có ai có thuật toán tốt hơn O(N^3) ko???
2014-06-30 11:04:57 Thang


Last edit: 2014-06-30 11:05:09
2013-07-09 02:01:29 Thủ khoa vãn
test aaaaaaba ra 2
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.