STEVESTRING - Rút gọn chuỗi

View as PDF

Submit solution


Points: 100.00
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Steve có một chuỗi S chỉ chứa các chữ cái a, bc, Steve được phép thực hiện thao tác sau vô số lần:

  • Lấy hai chữ cái khác nhau và đứng cạnh nhau trong chuỗi S và thay thế bằng chữ cái còn lại.

Hãy giúp Steve tìm độ dài chuỗi ngắn nhất có thể sau khi áp dụng thao tác trên.

Dữ liệu

  • Dòng đầu tiên chứa số test T (1T100).
  • Mỗi dòng trong số T dòng tiếp theo chứa chuỗi S (Độ dài chuỗi S100).

Kết quả

  • Với mỗi test case, in ra độ dài chuỗi ngắn nhất thu được.

Ví dụ

Sample Input 1
Copy
3
cab
bcab
ccccc
Sample Output 1
Copy
2 
1
5

Giải thích

  • Đối với test thứ nhất, có hai cách rút gọn S: cab −→ cc hoặc cab−→ bb.
  • Đối với test thứ hai, cách rút gọn tối ưu S: bcab −→ aab −→ ac −→ b.
  • Đối với test cuối, không thể thực hiện thao tác nào nên kết quả vẫn là dãy S.

Nguồn: Free Contest 124


Comments

Please read the guidelines before commenting.


There are no comments at the moment.