GAO - Siêu nhân GAO
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Các siêu nhân GAO gồm có 3 màu,  trắng (T), xanh (X) và đỏ (D). Ban đầu có tổng cộng n siêu nhân GAO đang sắp thành một hàng dọc với thứ tự màu lộn xộn. Khi có lệnh tập hợp, các siêu nhân phải đổi chỗ cho nhau (swap) sao cho màu trắng đứng đầu, màu xanh đứng giữa và màu đỏ đứng cuối. Bạn hãy tìm cách đổi chỗ các siêu nhân sao cho số lần đổi chỗ là ít nhất nhé.

Dữ liệu nhập:

- Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 105).

- Dòng tiếp theo gồm n ký tự T, X, D thể hiện màu của các GAO trong thứ tự sắp hàng ban đầu. Đề bài cho đảm bảo có đủ 3 màu.

Dữ liệu xuất:

- Dòng đầu tiên là số m, là tổng số lần đổi chỗ ít nhất.

- Trong m dòng tiếp theo, mỗi dòng gồm 2 số i và j là chỉ số vị trí của 2 siêu nhân cần đổi chỗ. i và j cách nhau một khoảng trắng. Nếu có nhiều cách đổi chỗ, in ra một cách bất kỳ.

Ví dụ

  • input
    6
    XXTDDD
    output
    1
    1 3
Back to Top