Xâu cuối cùng tinh tế nhất
Đề bài
Mô tả
FWMC nhận được một xâu độ dài , chỉ gồm các ký tự A và B, làm quà sinh nhật. Danh tính của người cứ tặng xâu cho FWMC vào mỗi dịp sinh nhật vẫn còn là một bí ẩn...
FWMC bắt đầu nghịch xâu này. FWMC có thể thực hiện thao tác nén sau trên xâu bao nhiêu lần tùy ý:
- Chọn một vị trí sao cho và (với là độ dài xâu hiện tại). Xóa hai ký tự và , rồi chèn vào vị trí vừa xóa một ký tự loại còn lại (chèn B nếu là A, và ngược lại).
FWMC cho rằng xâu có thứ tự từ điển càng nhỏ thì càng tinh tế. Xâu nhỏ hơn xâu theo thứ tự từ điển khi và chỉ khi một trong hai điều sau xảy ra:
- là tiền tố của và ;
- tại vị trí đầu tiên mà và khác nhau, ký tự của đứng trước ký tự của trong bảng chữ cái.
Hãy giúp FWMC tìm xâu tinh tế nhất có thể thu được từ xâu , cùng với một dãy thao tác nén để thu được xâu đó.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa số nguyên (): độ dài xâu .
- Dòng thứ hai chứa xâu , chỉ gồm các ký tự A và B.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra:
- Dòng thứ nhất chứa xâu : xâu tinh tế nhất có thể thu được từ xâu .
- Dòng thứ hai chứa số nguyên (): số thao tác nén.
- Dòng thứ ba chứa số nguyên biểu diễn thao tác. Giá trị nghĩa là thao tác thứ xóa hai ký tự ở vị trí và , rồi chèn ký tự mới vào vị trí . Giá trị phải nhỏ hơn độ dài của xâu trước thao tác này. Nếu , dòng này để trống.
Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- .
- , xâu chỉ gồm các ký tự A và B.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 B 3 BAA 5 ABBBA |
B 0 A 2 2 1 AA 3 3 3 2 |
Ở bộ dữ liệu thứ nhất, không thể thực hiện thao tác nào nên xâu tinh tế nhất là B. Ở bộ dữ liệu thứ hai, có thể thu được A (có thể chứng minh đây là xâu tinh tế nhất): BAA → BB → A. Ở bộ dữ liệu thứ ba, có thể thu được AA (có thể chứng minh đây là xâu tinh tế nhất): ABBBA → ABAA → ABB → AA. |
| 3 4 AAAB 4 ABAB 6 BAABAB |
AA 2 2 2 ABAB 0 AB 4 2 2 2 1 |
Ví dụ bổ sung (không có trong đề gốc). AAAB → ABB → AA. Xâu ABAB không có hai ký tự kề nhau giống nhau nên không thể nén. BAABAB → BBBAB → BAAB → BBB → AB. |
Bình luận