STREDUCE - String reduction
English | Tiếng Việt |
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 !
|
|
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.
|
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 |