Lần cuối

Points: 1600 (partial)

Time limit: 1.0s

Python 3 2.5s

Memory limit: 256M

Python 3 512M

Input: LAST.INP

Output: LAST.OUT

Author:

im_mayly

Problem type

Allowed languages

C++, Pascal, Python

Statement

Đoàn tàu âm nhạc gồm $6$ người đã cùng nhau trải qua bao nhiêu chặng đường từ năm $2013$ đến năm $2024$ , mỗi người được đảm nhiệm một vai trò khác nhau. Giờ đây, trong chuyến hành trình cuối cùng, cả nhóm dừng lại ở "ga chia tay". Dù có chút cay đắng nhưng không còn nỗi đau nào đọng lại, từng người dần xuống xe, để lại những âm hưởng cuối cùng của ban nhạc.

trước khi xuống xe, band đã nghe lại $t$ bài nhạc cùng nhau. Vì ai cũng muốn giai điệu càng dài càng tốt nên cả đội muốn nốt đen cần đứng sau tất cả các nốt trắng. Band đã cùng nhau "cắt" bài nhạc đó thành các phần nhỏ và sau đó ghép lại với nhau (tất cả nốt trắng đứng trước nốt đen).

Nhiệm vụ của bạn là hãy xác định số đoạn được cắt ít nhất để ban nhạc không lãng phí thời gian trong việc tận hưởng những giai điệu cuối.

Input, Output và Subtasks

Input: (LAST.INP)

Dòng đầu tiên chứa số nguyên $t$ tương úng với $t$ testcase.
$t$ dòng tiếp theo, mỗi dòng chứa $1$ xâu $S$ gồm các kí tự trong tập hợp { $W, B$ } tương ứng với nốt trắng và nốt đen của đoạn nhạc.

Output: (LAST.OUT)

Với mỗi testcase, in ra $1$ số nguyên duy nhất là số đoạn cắt được ít nhất.

Subtasks

Subtask chung: $t \leq 500$
Subtask 1 ( $05$ %): chuỗi toàn "W" hoặc "B";
Subtask 2 ( $15$ %): $1 \leq |S| \leq 10$ ;
Subtask 3 ( $30$ %): $1 \leq |S| \leq 100$ ;
Subtask 4 ( $50$ %): $1 \leq |S| \leq 1000$ ;

Sample #1

Input (LAST.INP)

3
BWBWB
BBBBB
WWWBB

Output (LAST.OUT)

4
1
1

Notes

với bộ test đầu tiên, ta có:
- BWBWB;
- B; W; B; WB;
- W; WB; B; B;
- WWBBB;
tổng số đoạn ít nhất được cắt ra là $4$ .
với bộ test thứ $2$ và thứ $3$ , tất cả các đoạn đã thỏa mãn điều kiện nên đáp án là đoạn ban đầu ( $1$ đoạn).

Comments

There are no comments at the moment.