2013
11-13

# Reverse

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}

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

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 1
3
Sample Input 2
4


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

//* @author:
import java.util.Scanner;

public class Main {
Scanner cin = new Scanner(System.in);
int n;

public void inPut() {
n = cin.nextInt();

reverse();
}

private void reverse() {
if (n == 1) {
System.out.println(0);
} else {
if (n == 2) {
System.out.println(1);
System.out.println(2 + " " + 1 + " " + 0);
} else {
if (n % 2 == 0) {
int m = (n + 1) / 2 + 1;
System.out.println(m);
print(n, m);
} else {
if(n % 2 != 0) {
int m = (n + 1) / 2;
System.out.println(m);
print(n, m);
}
}
}
}
}

void print(int n, int m) {
if (n % 2 != 0) {
for (int i = 0; i < m - 1; i++) {
System.out.println((n / 2 + i + 1) + " " + 2 + " " + i);
}
System.out.println(1 + " " + (n - 1) / 2 + " " + (n - 1) / 2);

} else {
for (int i = 0; i < m - 2; i++) {
System.out.println((n / 2 + i + 1) + " " + 2 + " " + (i + 1));
}
System.out.println(2 + " " + (n - 1) / 2 + " " + (n) / 2);
System.out.println(1 + " " + 1 + " " + (n - 1));

}
}

public static void main(String[] args) {
new Main().inPut();
}

}

2. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}