Subtask 1

Xem mỗi dãy màu bi của ~n+1~ là một trạng thái (có tổng cộng ~(n+1)!~ trạng thái), rồi thực hiện tìm đường đi ngắn nhất từ trạng thái ban đầu (~[a_1, a_2, \ldots, a_n, 0]~) đến trạng thái cuối cùng (~[1, 2, \ldots, n, 0]~) bằng thuật toán BFS.

Subtask 2

Ta có thể hoán đổi bi trên hai lỗ bi nằm kế nhau ~i~ và ~i+1~ bằng ~3~ thao tác di chuyển bi (~i \rightarrow n+1~, ~i+1 \rightarrow i~, ~n+1 \rightarrow i+1~). Do đó, ta có thể sử dụng thuật toán sắp xếp sau: chừng nào còn tồn tại vị trí ~i~ sao cho ~a_i > a_{i+1}~ thì ta sẽ hoán đổi bi trên hai lỗ ~i~ và ~i+1~. Cách làm này sẽ mất tối đa ~3 \times \frac{n(n-1)}{2}~ thao tác di chuyển bi.

Subtask 3

Với ~i < j~, ta có thể di chuyển bi từ lỗ ~j~ qua lỗ ~i~ rồi đẩy bi ở các lỗ ~i+1, \ldots, j~ sang phải một lỗ (giống như việc xóa đi ~a_j~ rồi chèn ~a_j~ vào trước phần tử ~a_i~ trong dãy ~a~) trong ~j-i+2~ thao tác như sau:

• ~i \rightarrow n+1~

• ~j-1 \rightarrow j, j-2 \rightarrow j-1, \ldots, i \rightarrow i+1~

• ~n+1 \rightarrow i~.

Do đó, ta có thể duyệt các màu bi ~x~ từ ~1~ đến ~n~, tìm lỗ bi ~p~ đang chứa bi màu ~x~, rồi thực hiện chèn bi từ lỗ ~p~ ra trước lỗ ~x~ theo mô tả như trên. Cách làm này sẽ mất tối đa ~\frac{n(n-1)}{2} + 2n~ thao tác di chuyển bi.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n+2, 0);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<pii> ops;
    auto make_op = [&](int s, int t) {
        ops.push_back({s, t});
        swap(a[s], a[t]);
    };

    for(int x = 1; x <= n; ++x) {
        for(int i = 1; i <= n; ++i) {
            if (a[i] == x) {
                make_op(i, n+1);
                for(int j = i; j > x; --j) {
                    make_op(j-1, j);
                }
                make_op(n+1, x);
            }
        }
    }

    cout << ops.size() << endl;
    for(auto e: ops) {
        cout << e.first << " " << e.second << endl;
    }
}

int main() {
    int t; cin >> t;
    while (t--) solve();

    return 0;
}