Loại bỏ one và two
Đề bài
Mô tả
Cho một xâu khác rỗng, chỉ gồm các chữ cái Latin thường.
Một xâu bị xem là "xấu" nếu nó chứa ít nhất một trong hai xâu con "one" hoặc "two". Nói cách khác, là xâu xấu nếu tồn tại chỉ số () sao cho "one" hoặc "two".
Bạn được phép chọn một tập các vị trí và xoá đồng thời tất cả các chữ cái tại những vị trí đó. Ví dụ, với "onetwone", nếu chọn hai vị trí và thì kết quả còn lại là "ontwne".
Hãy tìm số vị trí ít nhất cần xoá để xâu không còn là xâu xấu, và chỉ ra các vị trí đó.
Dữ liệu vào
- Dòng đầu chứa số nguyên - số lượng bộ dữ liệu.
- Mỗi bộ dữ liệu gồm một dòng chứa xâu khác rỗng, chỉ gồm chữ cái Latin thường.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra:
- Dòng đầu chứa số nguyên () - số vị trí ít nhất cần xoá.
- Dòng thứ hai chứa số nguyên phân biệt - các vị trí cần xoá (theo thứ tự bất kỳ), đánh số từ đến . Nếu thì dòng này có thể để trống.
Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- Tổng độ dài của tất cả các xâu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 onetwone testme oneoneone twotwo |
2 2 6 0 3 2 5 8 2 2 5 |
"onetwone" chứa "two" và "one" đan nhau ở chữ o; xoá 2 vị trí là đủ. "testme" đã tốt nên . "oneoneone" cần xoá 3 chữ. "twotwo" cần xoá 2 chữ. Đây chỉ là một trong nhiều đáp án hợp lệ. |
| 4 two one twone abc |
1 2 1 2 1 3 0 |
Với "twone", hai xâu con "two" và "one" dùng chung chữ o ở vị trí 3, nên chỉ cần xoá đúng vị trí 3 là loại được cả hai. "abc" không cần xoá. |
Bình luận