STREDUCE - String reduction

no tags 

Cho một xâu chỉ gồm hai loại kí tự 'a' và 'b'. Bạn có thể thực hiện phép rút gọn xâu như sau: thay thế một xâu con dạng a?a hoặc b?b thành ?, trong đó ? thể hiện cho một kí tự bất kì.

Yêu cầu

Tìm cách rút gọn xâu cho trước thành một xâu với độ dài nhỏ nhất có thể, chỉ ra độ dài đó.

Dữ liệu

- Gồm một dòng duy nhất ghi xâu ban đầu.

Kết quả

- Gồm một số duy nhất là độ dài nhỏ nhất tìm được.

Ví dụ

Dữ liệu:
baaba

Kết quả:
1

Giới hạn

- Độ dài xâu ban đầu không quá 300.


hide comments
Utkarsh Agarwal: 2016-02-11 14:15:00

can answer be anything different than 1, 2 or length ?? if yes case pls

Sudharsansai: 2015-03-30 14:59:10

Very nice question....

vishal johri: 2014-10-16 07:34:31

I am getting WA even though my solution looks correct! ..Kindly post some tricky testcases so that I can verify my answer..Thanks!

amit: 2012-06-17 18:42:10

tough!!

Last edit: 2012-06-17 18:42:48
Samiul Saeef: 2012-04-04 17:38:30

n^3 dp AC passes in 3.11 sec

M Misbachul Huda: 2011-11-07 23:17:13

I still geting WA, please help me !
:(
please give me more testcase

Supreeth: 2011-10-20 09:41:48

O(n*8) worked

Prabakaran: 2011-02-13 13:51:27

will O((n^3)*25) solution pass?

sudipto das: 2011-01-17 16:14:06

Pawel Gawrychowski is right...After getting several WA, i noticed his post and finally got ac... So,DONT USE GETS().

[Trichromatic] XilinX: 2009-08-20 10:59:49

I've found that this problem originally comes from NEERC 2001, Western Subregion.

Re: Yes, I confirm your information right! I will alter the problem and the source suitably, sorry for the inconvenience.

Last edit: 2009-08-20 10:57:08

Added by:AnhDQ
Date:2009-06-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NEERC 2001 - Western Subregion