Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Reverse
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 3263Accepted: 1052Special Judge

Description

You will be given a list of n integers S = {1, 2, ... , (n-1), n}, please write a program to calculate the minimum number of instructions required to change the list in descending order {n, (n-1), ..., 1}. Let S[i] denote the i-th element of S, 1 ≤ in.

Each instruction takes a successive subsequence and removes that subsequence from the list, then insert that subsequence into any position of the list as a parameter. Each instruction can be represented by three numbers (pos1,length,pos2),which means we will remove subsequence S[pos1] ..... S[pos1+length-1], then insert them after the S[pos2] (pos2=0 will insert it at the beginning). We always have: 1 ≤ pos1n, 1 ≤ lengthn+1-pos1, 0 ≤ pos2n-length

For example:
The list S = {4,6,5,3,1,2},instruction (2,3,0) to get {6,5,3,4,1,2}
The list S = {4,6,5,3,1,2},instruction (3,1,2) to get {4,6,5,3,1,2}
The list S = {4,6,5,3,1,2},instruction (4,3,1) to get {4,3,1,2,6,5}
The list S = {4,6,5,3,1,2},instruction (2,4,2) to get {4,2,6,5,3,1}

Input

The input contains one integer n. 1 ≤ n ≤ 100

Output

The first line of output contains one integer C denoting the number of instructions.
Following C lines, each contains three numbers (pos1, length, pos2) for one instruction. If there are many such instructions, you can output any one of them.

Sample Input

Sample Input 1
3
Sample Input 2
4

Sample Output

Sample Output 1
2
1 1 2
1 1 1
Sample Output 2
3
1 2 2
1 1 1
3 1 3

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator