Chuyển đổi dãy số

Xem PDF

Điểm: 600 (p) 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à các phần tử được sắp xếp tăng dần từ \(1\) đến \(n\) (Tức là \(A[]=\left\{1,2,3,...,n\right\}\)). Nhiệm vụ của bạn là in ra số tập lệnh tối thiểu để chuyển mảng \(A\) thành mảng gồm các phần tử được sắp xếp theo thứ tự giảm dần (Tức là, sau khi biến đổi: \(A[]=\left\{n,n-1,n-2,...,1\right\}\))

Mảng \(A\) được đánh chỉ số bắt đầu từ \(1\).

Mỗi tập lệnh có cấu trúc như sau: \((p_1,len,p_2)\). Điều kiện \(1\) \(\leq\) \(p_1\) ; \(1\) \(\leq\) \(len \leq\) \(n+1 - p_1\) ; \(0\) \(\leq\) \(p_2\) \(\leq\) \(n\) \(-\) \(len\)

Ta áp dụng các tập lệnh đó vào \(A\) như sau: Lấy subarray (có nghĩa là mảng con gồm các phần tử liên tiếp) từ vị trí \(p_1\) đến \(p_1+len-1\), sau đó xóa chúng đi và thêm lại vào phía sau vị trí \(p_2\). Nếu \(p_2=0\), thì ta hiểu subarray đó được thêm vào phía trước đầu tiên của mảng \(A[]\).

Ví dụ: Giả sử ta có mảng \(A[]=1,2,3\), áp dụng tập lệnh \((1,1,2)\) vào \(A\), ta có quá trình biến đổi như sau:

  • Ta tìm được \(subarray[]=1\).

  • Xóa đi subarray này, thì mảng \(A\) còn lại: \(A[]=2,3\)

  • Thêm subarray này lại vào vị trí sau vị trí thứ \(2\), ta được \(A[]=2,3,1\).

Hoặc giả sử ta áp dụng tập lệnh \((2,2,0)\). Khi đó \(A[]\) sẽ trở thành \(A[]=2,3,1\).

Yêu cầu: Cho số nguyên dương \(n\). In ra số tập lệnh tối thiểu cần dùng, và liệt kê chúng ra. Nếu có nhiều đáp án, in ra bất kì.

Input

  • Nhập số \(n(1\leq n\leq 1000)\).

Output

  • Dòng thứ nhất chứa số tập lệnh tối thiểu cần dùng.

  • In ra các dòng liệt kê số tập lệnh trên, mỗi tập lệnh một dòng.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(1\leq n \leq 100\).
  • Subtask \(2\) (\(70\%\) số điểm): \(101\leq n \leq 1000\).

Example

Test 1

Input
3 
Output
2
1 1 2
1 1 1
Note
  • Ban đầu: \(A[]=1,2,3\)

  • Sau khi áp dụng "tập lệnh" thứ nhất, \(A\) trở thành: \(A[]=2,3,1\)

  • Sau khi áp dụng "tập lệnh" thứ hai, \(A\) trở thành: \(A[]=3,2,1\).


Bình luận


  • 0
    tuanlinh    10:16 p.m. 19 Tháng 7, 2020

    xin 1 đáp án với n=5


    • 0
      jumptozero    8:14 a.m. 20 Tháng 7, 2020 chỉnh sửa 3

      Đây @tuanlinh

      3

      2 2 3

      1 2 2

      2 2 3