#include "stdio.h"
#include "math.h"
#define N 4999
int m,a[100],x,y,q[100]={0};
struct 
{char q[10];}u[6]={"fcfs","scan","look","c-scan","c-look","sstf"};
input()
{int i;
 printf("plese input the number of the positions that the cylinder is to go:");
 scanf("%d",&m);
 printf("Input the positions:\n");
  for(i=0;i<m;i++)
  scanf("%d",&a[i]);
 printf("Input the prior and the present position:\n");
  scanf("%d%d",&x,&y); 

}
fcfs()
{int i;
 int distance=0;
 printf("The fcfs path is:\n");
 printf("%d",y);
 for(i=0;i<m;i++)
 printf("->%d",a[i]);
 printf("\n");
 if(a[0]>=y) distance=a[0]-y;
 else distance=y-a[0];
 for(i=0;i<m-1;i++)
  {if(a[i]<a[i+1])
    distance=distance+a[i+1]-a[i];
   else distance=distance+a[i]-a[i+1];
  }
  printf("The fcfs total distance is:%d\n",distance);
  q[0]=distance;
  }
scan()
{int i,j,k,s,p,b[100]={0},c[100]={0},distance=0;
 if(x>y) 
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]<=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The scan path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]<b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
      printf("->0");
    for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]>c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]);  
    distance=y+c[k-1];
    printf("\nThe scan total distance is:%d\n",distance);
  } 
 else
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]>=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The scan path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]>b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
     printf("->%d",N);  
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]<c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]); 
   distance=N-y+N-c[k-1];
    printf("\nThe scan total distance is:%d\n",distance);     	
  }  
 q[1]=distance;
}
look()
{int i,j,s,k,p,b[100]={0},c[100]={0},distance=0;
 if(x>y) 
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]<=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The look path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]<b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]>c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]);  
    if(b[0]==0) distance=c[k-1]-y;
    else distance=y-2*b[j-1]+c[k-1];
    printf("\nThe look total distance is:%d\n",distance);	
  } 
 else
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]>=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The look path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]>b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]);   
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]<c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]); 
    if(b[0]==0) distance=y-c[k-1];
   else distance=2*b[j-1]-y-c[k-1];
    printf("\nThe look total distance is:%d\n",distance);        	
  }  
  q[2]=distance;
}
cscan()
 {int i,j,k,s,p,b[100]={0},c[100]={0},distance=0;
 if(x>y) 
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]<=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The cscan path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]<b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
      printf("->0");
      printf("->%d",N);
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]<c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]);  
    distance=y+2*N-c[k-1];
    printf("\nThe cscan total distance is:%d\n",distance);
  } 
 else
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]>=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The cscan path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]>b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
     printf("->%d",N);
     printf("->0");  
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]>c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]); 
   distance=N-y+N+c[k-1];
    printf("\nThe cscan total distance is:%d\n",distance);  	
  }  
  q[3]=distance;
 }
clook()
{int i,j,s,k,p,b[100]={0},c[100]={0},distance=0;
 if(x>y) 
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]<=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The clook path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]<b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]); 
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]<c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]);  
    if(b[0]==0) distance=2*c[0]-c[k-1]-y;
    if(c[0]==0) distance=y-b[j-1];
    if((b[0]!=0)&&(c[0]!=0)) distance=2*c[0]+y-2*b[j-1]-c[k-1];
    printf("\nThe clook total distance is:%d\n",distance);	
  } 
 else
  {for(i=0,j=0,k=0;i<m;i++) 
  	{if(a[i]>=y) 
  	 {b[j]=a[i]; j++;}
  	else 
  	 {c[k]=a[i]; k++;}
  	}
  	printf("The clook path is:\n");
  	printf("%d",y);
    for(i=0;i<j;i++)
     for(s=i+1;s<j;s++)
      if(b[i]>b[s])
       { p=b[i];
      	b[i]=b[s];
        b[s]=p;
        }
     for(i=0;i<j;i++)
      printf("->%d",b[i]);   
   for(i=0;i<k;i++)
     for(s=i+1;s<k;s++)
      if(c[i]>c[s])
      { p=c[i];
      	c[i]=c[s];
        c[s]=p;
      }
    for(i=0;i<k;i++)  
       printf("->%d",c[i]); 
    if(c[0]==0) distance=b[j-1]-y;
    if(b[0]==0) distance=c[k-1]-2*c[0]+y;
    if((c[0]!=0)&&(b[0]!=0)) distance=2*b[j-1]-y+c[k-1]-2*c[0];
    printf("\nThe clook total distance is:%d\n",distance);        	
  }  
  q[4]=distance;
}
sstf()
{int t,r,i,j,distance=0;
  t=y;
  printf("The sstf path is:\n");
  printf("%d",y);
  for(i=0;i<m;i++)
   {for(j=i+1;j<m;j++)
    {if(abs(a[j]-t)<abs(a[i]-t))
      {r=a[i];
      a[i]=a[j];
      a[j]=r;
      }
    }  
      distance+=abs(a[i]-t);
      t=a[i];
    printf("->%d",a[i]);	 
   } 
  printf("\nThe sstf total distance is:%d\n",distance); 
  q[5]=distance; 
}
shortest()
{int i,j,p;
	fcfs();scan();cscan();look();clook();sstf();
	for(j=0;j<6;j++)
     {for(i=j+1;i<6;i++)
      if(q[j]>q[i])
       { p=q[j];
      	q[j]=q[i];
        q[i]=p;
        u[6]=u[j];
      	u[j]=u[i];
        u[i]=u[6];
       }
     }
 printf("\nshortest======================>>longest\n");
 printf("%s%8s%8s%8s%8s%8s\n",u[0].q,u[1].q,u[2].q,u[3].q,u[4].q,u[5].q);
 printf("%d%8d%8d%10d%10d%10d\n",q[0],q[1],q[2],q[3],q[4],q[5]);
 }
main()
{int ch;
l2: input();
 printf("==========================================================\n");
 printf("\nPlease choise a algorithm:\n");
 printf("1.fcfs\n");
 printf("2.scan\n");
 printf("3.c-scan\n");
 printf("4.look\n");
 printf("5.c-look\n");
 printf("6.sstf\n");
 printf("7.input again\n");
 printf("8.choose the shortest distance algorithm\n");
 printf("0.exit\n");
 printf("==========================================================\n");
l1: ch=getche();
 printf("\n");
 switch(ch)
 {case '1':fcfs(); break;
  case '2':scan(); break;
  case '3':cscan(); break;
  case '4':look(); break;
  case '5':clook(); break;
  case '6':sstf(); break;
  case '7':goto l2; break;
  case '8':shortest();break;
  case '0':exit();
  default:printf("input error,please input again:");goto l1;
 }
 printf("\n");
 printf("==========================================================\n");
 printf("\nPlease choise a algorithm:\n");
 printf("1.fcfs\n");
 printf("2.scan\n");
 printf("3.c-scan\n");
 printf("4.look\n");
 printf("5.c-look\n");
 printf("6.sstf\n");
 printf("7.input again\n");
 printf("8.choose the shortest distance algorithm\n");
 printf("0.exit\n");
 printf("==========================================================\n");
 goto l1;
}