Sắp xếp đồng thời

Xem PDF

Điểm: 600 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho mảng \(A\) gồm \(n\) phần tử và ta có một phép toán như sau:

  • Cùng một lúc ta có thể chọn nhiều cặp khác nhau và hoán đổi vị trí chúng cho nhau (Biết rằng các cặp này không được giao nhau).

Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán trên để dãy đã cho không giảm.

Input

  • Dòng thứ nhất chứa số nguyên \(n(1\le n\le 1000)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^9)\)

Output

  • Dòng thứ nhất chứa số \(k\) - số phép toán tối thiểu cần dùng

  • \(k\) dòng tiếp theo, mỗi dòng in ra có dạng như sau: \(p\text{ }i_1\text{ }j_1 \text{ }i_2\text{ }j_2...i_p\text{ }j_p\). Trong đó \(p\) là số cặp ta chọn để hoán đổi vị trí, tiếp theo là \(p\) cặp \((i_u,j_u)(1\le u\le p;i_u\ne j_u)\) thể hiện chỉ số của cặp cần hoán đổi vị trí cho nhau. (Chú ý: Hai cặp chỉ số \(A,B\) gọi là giao nhau nếu tồn tại số \(k\) thỏa mãn \(k\in A\)\(k\in B\)). Nếu có nhiều đáp án, in ra đáp án bất kì.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(1\le n\le 10\)

  • Subtask \(1\) (\(60\%\) số điểm): Còn lại

Example

Test 1

Input
3
1 3 2 
Output
1
1 2 3
Note

Giải thích: Ta chỉ cần chọn một cặp đó là \((2,3)\) thì sẽ được dãy không giảm là \(1,2,3\)


Bình luận


  • 0
    new4letuantu    2:59 p.m. 20 Tháng 2, 2021

    Nếu có nhiều đáp án, in ra đáp án bất kì.
    cko em 1 VD dc ko