1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <stdio.h>
using namespace std;
int x[10],n,u,v,tmpa,tmpb;
void Move(int a,int b){
    tmpa=x[a],tmpb=x[a+1];
    if(a>b){
        for(u=b;u<a;u++)x[u+2]=x[u];
        x[b]=tmpa;x[b+1]=tmpb;
    }
    else{
        for(u=a+2;u<b+2;u++)x[u-2]=x[u];
        x[b]=tmpa;x[b+1]=tmpb;
    }
}
int cal(int lv,int len){
    if(lv>15)return -1;
    int i,j,a,b,k,Min=100,tmp;
    for(i=0;i<n;i++)if(x[i]!=i+1)break;
    if(i==n)return lv;
    if(x[0]==len){
        if(len<3)return -1;
        for(i=1;i<len-1;i++){
            Move(i,0);
            tmp=cal(lv+1,len-1);
            if(tmp>0)Min=min(Min,tmp);
            Move(0,i);
        }
        return Min==100?-1:Min;
    }
    for(i=0;i<len;i++){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX