Xâu bằng nhau
Đề bài
Mô tả
Cho hai xâu và , đều có độ dài và chỉ gồm các chữ cái Latin thường, cùng một số nguyên .
Bạn muốn biến xâu thành xâu bằng cách thực hiện một số (có thể bằng ) thao tác lên . Mỗi thao tác là một trong hai loại sau:
- Chọn một chỉ số () rồi đổi chỗ và .
- Chọn một chỉ số () sao cho ký tự liên tiếp đều bằng cùng một ký tự với , rồi thay tất cả chúng bằng ký tự liền sau (tức là 'a' thành 'b', 'b' thành 'c', ..., 'y' thành 'z').
Các thao tác chỉ được thực hiện trên xâu , và có thể thực hiện với số lần tùy ý. Hãy xác định liệu có thể biến thành hay không.
Dữ liệu vào
- Dòng đầu chứa số nguyên là số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm ba dòng:
- Dòng thứ nhất chứa hai số nguyên và .
- Dòng thứ hai chứa xâu độ dài .
- Dòng thứ ba chứa xâu độ dài .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra "Yes" nếu có thể biến thành , ngược lại in ra "No". Có thể in bằng chữ hoa hoặc thường tùy ý.
Ràng buộc
- Tổng của trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 3 abc bcd 4 2 abba azza 2 1 zz aa 6 2 aaabba ddddcc |
No Yes No Yes |
Bộ 2: abba, tăng cặp bb rồi cặp cc... cho đến khi thành azza (đổi chỗ đưa hai ký tự giống nhau cạnh nhau rồi tăng). Bộ 3: chỉ có thể tăng ký tự, không thể giảm zz thành aa. Bộ 4: aaabba, đổi chỗ thành aaaabb rồi tăng dần các cặp để được ddddcc. |
| 3 2 2 aa cc 4 3 aaaa dddd 5 5 aaaaa bbbbb |
Yes No Yes |
Bộ 1: aa tăng thành bb rồi cc. Bộ 2: cần tăng cả 4 ký tự a lên d nhưng mỗi lần chỉ tăng đúng khối 3 ký tự giống nhau, 4 không chia hết cho 3 nên không thể. Bộ 3: cả khối 5 ký tự a được tăng một lần lên b. |
Bình luận