Xâu Tốt
Đề bài
Mô tả
Cho một xâu độ dài chỉ gồm hai loại ký tự > và <. Bạn có thể thực hiện một loạt thao tác trên xâu, mỗi thao tác chọn một ký tự còn lại trong xâu:
- Nếu chọn ký tự
>, thì ký tự đứng ngay sau nó bị xoá (nếu ký tự được chọn là ký tự cuối cùng, không có gì xảy ra). - Nếu chọn ký tự
<, thì ký tự đứng ngay trước nó bị xoá (nếu ký tự được chọn là ký tự đầu tiên, không có gì xảy ra).
Xâu được gọi là tốt nếu tồn tại một dãy thao tác sao cho sau khi thực hiện chỉ còn lại đúng một ký tự.
Trước khi thực hiện các thao tác, bạn có quyền xoá bớt một số ký tự trong xâu ban đầu (có thể không xoá ký tự nào, nhưng không được xoá hết — phải còn ít nhất một ký tự).
Hãy tính số ký tự ít nhất cần xoá để xâu trở thành xâu tốt.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên — số lượng bộ test.
Mỗi bộ test gồm hai dòng:
- Dòng thứ nhất chứa số nguyên — độ dài xâu.
- Dòng thứ hai chứa xâu độ dài , chỉ gồm các ký tự
>và<.
Dữ liệu ra
Với mỗi bộ test, in ra một dòng chứa số ký tự ít nhất cần xoá để xâu trở thành xâu tốt.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 <> 3 ><< 1 > |
1 0 0 |
Test 1: xoá một ký tự bất kỳ trong <> để còn lại một ký tự. Test 2: xâu ><< đã tốt — thao tác > < < → < < → <. Test 3: xâu chỉ có một ký tự nên đã tốt. |
| 1 5 <<>>> |
2 | Cần xoá ký tự < ở đầu để được >>>, sau đó dùng các > ăn dần về bên phải. |
Bình luận