CSES - Letter Pair Move Game | Trò chơi di chuyển cặp kí tự

Xem PDF
Tác giả:
nhphucqt
Dạng bài
Đ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, B hoặ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


  • 0
    Thanh72    10:23 p.m. 18 Tháng 8, 2023 ← chỉnh sửa 2

    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 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 dương \(n (n \leq 100)\).
    • Dòng thứ hai là xâu gồm \(2n\) kí tự. Mỗi kí tự có thể là A, B hoặ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 \leq 1000\)
    • Nếu không có giải pháp, in ra \(−1\).

    Test 1

    Input 
    3  
AB..BA
    Output 
    2
ABBA..
A..ABB

    Test 2

    Input 
    3
ABAB..
    Output 
    -1