CSES - Letter Pair Move Game | Trò chơi di chuyển cặp kí tự
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(2n\) hộp trên một hàng thẳng. Có đúng hai hộp trống và đứng liền kề nhau, tất cả các hộp còn lại chứa chữ cái A hoặc B. Mỗi chữ cái xuất hiện trong đúng \(n-1\) ô.
Nhiệm vụ của bạn là di chuyển các chữ cái để tất cả các chữ cái A xuất hiện trước bất kỳ chữ cái B nào. Ở mỗi lượt, bạn có thể chọn bất kỳ hai ô liền kề nào đều chứa chữ cái và di chuyển các chữ cái đến hai ô trống liền kề trong hàng, giữ nguyên thứ tự của chúng.
Có thể chứng minh rằng có một giải pháp có nhiều nhất \(10n\) lượt hoặc không có giải pháp nào.
Input
- Dòng đầu chứa số nguyên \(n\): \(2n\) ô.
- Dòng thứ hai là xâu gồm \(2n\) kí tự. Mỗi kí tự có thể là
A,Bhoặc.(hộp rỗng).
Output
- Dòng đầu in ra số nguyên \(k\) thể hiện số lượt thay đổi.
- \(k\) dòng sau, mỗi dòng in ra 1 xâu độ dài \(2n\) thể hiện xâu sau lượt thay đổi thứ \(i\). Bạn có thể in ra bất kì giải pháp nào, miễn là \(k \le 1000\).
- Nếu không có giải pháp, in ra \(-1\).
Constraints
- \(1 \le n \le 100\)
Example
Sample input 1
3
AB..BA
Sample output 1
2
ABBA..
A..ABB
Sample input 2
3
ABAB..
Sample output 2
-1
Bình luận
Có \(2n\) hộp được đặt trên một hàng thẳng. Trong số đó, có đúng hai hộp trống và đứng liền kề nhau, tất cả các hộp còn lại chứa chữ cái
AhoặcB. Mỗi chữ cái xuất hiện trong đúng \(n−1\) ô.Nhiệm vụ của bạn là di chuyển các chữ cái để tất cả các chữ cái
Axuất hiện trước bất kỳ chữ cáiBnào. Ở mỗi lượt, bạn có thể chọn bất kỳ hai ô liền kề nào đều chứa chữ cái và di chuyển các chữ cái đến hai ô trống liền kề trong hàng, giữ nguyên thứ tự của chúng.Có thể chứng minh rằng có một giải pháp có nhiều nhất \(10n\) lượt hoặc không có giải pháp nào.
Input
A,Bhoặc.(Hộp rỗng).Output
Test 1
Input
Output
Test 2
Input
Output