Elearning CodePath – CTP Online Judge

TYPING

🟢 Easy #String #Greedy

---

### 📝 Bài toán
Trong tiết Tin học, Tài được học cách gõ ba ký tự trong tên của mình là T, A, I. Trong Q ngày tới, mỗi ngày Tài nhận được một xâu S_i gồm ba ký tự nêu trên để luyện tập.

Tài chỉ có thể gõ được hai ký tự A và T bằng tay trái, hai ký tự T và I bằng tay phải. Nghĩa là khi bắt đầu một xâu, Tài có thể chọn dùng một trong hai tay để gõ, sau đó trong quá trình gõ, Tài phải đổi giữa hai tay nếu cần thiết để gõ được hết các ký tự trong xâu theo đúng thứ tự.

Ký hiệu F(S) là số lần ít nhất Tài phải đổi tay để gõ hết xâu S.

Hãy xét hai giá trị S_i và X_i là xâu ký tự và câu hỏi Tài muốn giải đáp vào ngày thứ i:
- Nếu X_i = 0: Tính giá trị F(S_i).
- Nếu X_i = 1: Tính tổng F(p) với p là tất cả các xâu con liên tiếp của S_i.

Vì đáp án có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho 10^9 + 7.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file văn bản TYPING.INP:
- Dòng đầu gồm một số nguyên Q (1 <= Q <= 100).
- Q dòng tiếp theo, mỗi dòng gồm một số nguyên X_i (0 <= X_i <= 1) và một xâu S_i (1 <= độ dài S_i <= 10^5).
- Tổng độ dài các xâu S_i không vượt quá 4 * 10^6.

### 📤 Định dạng Đầu ra
Ghi ra file văn bản TYPING.OUT Q dòng, mỗi dòng là đáp án tương ứng của ngày thứ i.

### ✨ Ví dụ
| TYPING.INP | TYPING.OUT | Giải thích |
| :--- | :--- | :--- |
| 4 | 0 | Ngày 1: F("I") = 0 (dùng tay phải). |
| 0 I | 2 | Ngày 2: F("ATIA") = 2 (Trái(A,T) -> Phải(I) -> Trái(A)). |
| 0 ATIA | 5 | Ngày 3: Tổng F(p) của các xâu con "ATIA" là 5. |
| 1 ATIA | 8 | Ngày 4: Tổng F(p) của các xâu con "TAIIII" là 8. |
| 1 TAIIII | | |

### 🏷 Subtasks
- Subtask 1 (40% số điểm): X_i = 0 với mọi i.
- Subtask 2 (40% số điểm): Xâu S_i không chứa ký tự T.
- Subtask 3 (20% số điểm): Không có ràng buộc bổ sung.

✅ Đã AC: 5 / 16 submissions