// SortTest.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <stdlib.h>
#include <tchar.h>
#include <iostream>
#include <vector>
#include "string.h"

#define bufferSize 20000
#define MAX_ELEMENTS 400
#define LONG_MAX 2147483647

struct myPair
{
	short a;
	short b;
};

long myBestResult = LONG_MAX;
std::vector<myPair> tempResult;
std::vector<myPair> bestResult;

void checkResult(long currentResult)
{
	if (currentResult<myBestResult)
	{
		myBestResult = currentResult;
		bestResult.clear();
		for (int i=0; i<tempResult.size(); i++) bestResult.push_back(tempResult[i]); 
	}
	tempResult.clear();
}


void saveResult()
{
	FILE* out;
    out = fopen("sorting.out","w");	
	fprintf(out,"%d\n",bestResult.size());
	for(int z=0; z<bestResult.size(); z++)
    {
		fprintf(out,"%d %d\n",bestResult[z].a,bestResult[z].b);
    }
    fclose(out);
}


bool loadInput(char* fileName)
{
	char tempBuffer[bufferSize];

	int N = 0;
	short myData[MAX_ELEMENTS];
	short myDataOrg[MAX_ELEMENTS];
	int CostPostitionType = 0;
	int CostValueType = 0;

	short CostPosition[MAX_ELEMENTS*MAX_ELEMENTS];
	short CostValue[MAX_ELEMENTS*MAX_ELEMENTS];


	FILE* in;
    char* next = NULL;
    char* c;
    int d;
    int idx;
	int i,j;
    
	in=fopen(fileName,"r");
	if (in==NULL) return false;
	
	if(fgets(tempBuffer,bufferSize,in))
    {
         sscanf (tempBuffer,"%d",&N);
    }

    fgets(tempBuffer,bufferSize,in);
    c = tempBuffer;
    idx = 0;
    do
    {
      next = strstr(c," ");
      if (next) next[0] = 0;
      d = atoi(c);
      c = next+1;
      myDataOrg[idx] = d;
      idx++;
    }while(idx<N && next);


	fgets(tempBuffer,bufferSize,in);
    sscanf (tempBuffer,"%d",&CostPostitionType);
    for(i=0;i<N;i++){
		fgets(tempBuffer,bufferSize,in);
		c = tempBuffer;
		idx = 0;
		int start=i*N;
		do
		{
		  next = strstr(c," ");
		  if (next) next[0] = 0;
		  d = atoi(c);
		  c = next+1;
		  CostPosition[start+idx] = d;
		  idx++;
		}while(idx<N && next);
	}


	fgets(tempBuffer,bufferSize,in);
	sscanf (tempBuffer,"%d",&CostValueType);
    for(i=0;i<N;i++){
		fgets(tempBuffer,bufferSize,in);
		c = tempBuffer;
		idx = 0;
		int start=i*N;
		do
		{
		  next = strstr(c," ");
		  if (next) next[0] = 0;
		  d = atoi(c);
		  c = next+1;
		  CostValue[start+idx] = d;
		  idx++;
		}while(idx<N && next);
	}    
   fclose(in);	


   short a,b;
   long price = 0;
   int totalSwaps = 0;

   //bubblesort
   memcpy(myData,myDataOrg, N*sizeof(short));
   for (i = 0; i < N-1; i++)       
   {
       for (j = 0; j < N-i-1; j++)  
	   {
           short j1 = j+1;
		   if (myData[j] > myData[j1]) 
		   {
			   totalSwaps++;
			   a = myData[j];
			   b = myData[j1];
			   myData[j] = b;
			   myData[j1] = a;
			   price += CostPosition[j*N+j1];
			   if (CostValueType)  
			   {
				   price += CostValue[(a-1)*N+b-1];
			   }
			   myPair pair;
			   pair.a = j+1;
			   pair.b = j1+1;
			   tempResult.push_back(pair);
			   printf("%d %d\n",j+1, j1+1);
		   }
	   }
   }
   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);


   //bubblesort optimized
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));
   for (i = 0; i < N-1; i++)       
   {
       for (j = 0; j < N-i-1; j++)  
	   {
			if(myData[j] == j+1) continue; //place ok
		   short j1 = j;
		   do{
			   j1++;
		   }while(myData[j1] == j1+1); //first out of order
		   if (myData[j] > myData[j1]) 
		   {
			   totalSwaps++;
			   a = myData[j];
			   b = myData[j1];
			   myData[j] = b;
			   myData[j1] = a;
			   price += CostPosition[j*N+j1];
			   if (CostValueType)  
			   {
				   price += CostValue[(a-1)*N+b-1];
			   }
			   myPair pair;
			   pair.a = j+1;
			   pair.b = j1+1;
			   tempResult.push_back(pair);
			   printf("%d %d\n",j+1, j1+1);
		   }
	   }
   }
   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);

  //bubblesort reversed
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));
   for (i = 0; i < N-1; i++)
   {
       for (j = N-1; j > i ; j--)  
	   {
			short j1 = j-1;
		   if (myData[j] < myData[j1]) 
		   {
			   totalSwaps++;
			   a = myData[j];
			   b = myData[j1];
			   myData[j] = b;
			   myData[j1] = a;
			   price += CostPosition[j*N+j1];
			   if (CostValueType)  
			   {
				   price += CostValue[(a-1)*N+b-1];
			   }
			   myPair pair;
			   pair.a = j+1;
			   pair.b = j1+1;
			   tempResult.push_back(pair);
			   printf("%d %d\n",j+1, j1+1);
		   }
	   }
   }
   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);


  //bubblesort reversed optimized
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));
   for (i = 0; i < N-1; i++)
   {
       for (j = N-1; j > i ; j--)  
	   {
			if(myData[j] == j+1) continue; //place ok
		   short j1 = j;
		   do{
			   j1--;
		   }while(myData[j1] == j1+1); //first out of order

		   if (myData[j] < myData[j1]) 
		   {
			   totalSwaps++;
			   a = myData[j];
			   b = myData[j1];
			   myData[j] = b;
			   myData[j1] = a;
			   price += CostPosition[j*N+j1];
			   if (CostValueType)  
			   {
				   price += CostValue[(a-1)*N+b-1];
			   }
			   myPair pair;
			   pair.a = j+1;
			   pair.b = j1+1;
			   tempResult.push_back(pair);
			   printf("%d %d\n",j+1, j1+1);
		   }
	   }
   }
   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);


  //best move 
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));   
   bool mixed = false;
   do
   {
	   mixed = false;
	   int bestIdx1 = -1;
	   int bestIdx2 = -1;
	   long tmpBestMoveCost = LONG_MAX;
	   for (i = 0; i < N; i++)
	   {
		   a = i+1; 
		   if (myData[i] == a)  continue; //ok
		   mixed = true;
		
		   for(j=0; j<N; j++)
		   {
			   if (myData[j] == a) 
			   {
				   int moveCost = CostPosition[j*N+i];
				   if (CostValueType)  
					{
						b = myData[i];
						moveCost += CostValue[(a-1)*N+b-1];
					}

				   if (moveCost<tmpBestMoveCost)
				   {
					   tmpBestMoveCost = moveCost;
					   bestIdx1 = i;
					   bestIdx2 = j;
				   } else if (moveCost==tmpBestMoveCost)
				   {
					   int d1 = abs(bestIdx1-bestIdx2);
					   int d2 = abs(i-j);
					   if (d1 > d2)
					   {
						   bestIdx1 = i;
						   bestIdx2 = j;
					   } else if (d1 == d2)
					   {
						   if (bestIdx1+bestIdx2 > i+j)
						   {
							   bestIdx1 = i;
							   bestIdx2 = j;
						   }
					   }
				   }
			   }
		   }
	   }

		if (mixed)
		{
			totalSwaps++;
			price+=tmpBestMoveCost;
			a = myData[bestIdx1];
			b = myData[bestIdx2];
			myData[bestIdx1] = b;
			myData[bestIdx2] = a;

			myPair pair;
			pair.a = bestIdx1+1;
			pair.b = bestIdx2+1;
			tempResult.push_back(pair);
			printf("%d %d\n",bestIdx1+1, bestIdx2+1);
		}

   }while(mixed);

   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);


  //best move by min distance
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));   
   mixed = false;
   do
   {
	   mixed = false;
	   int bestIdx1 = -1;
	   int bestIdx2 = -1;
	   long tmpBestMoveCost = LONG_MAX;
	   for (i = 0; i < N; i++)
	   {
		   a = i+1; 
		   if (myData[i] == a)  continue; //ok
		   mixed = true;
		
		   for(j=0; j<N; j++)
		   {
			   if (myData[j] == a) 
			   {
				   short moveDistance = abs(j-i);
				   if (moveDistance<tmpBestMoveCost)
				   {
					   tmpBestMoveCost = moveDistance;
					   bestIdx1 = i;
					   bestIdx2 = j;
				   } else if (moveDistance==tmpBestMoveCost)
				   {
						if (bestIdx1+bestIdx2 > i+j)
						{
							bestIdx1 = i;
							bestIdx2 = j;
						}
				   }
			   }
		   }
	   }

		if (mixed)
		{
			totalSwaps++;
			a = myData[bestIdx1];
			b = myData[bestIdx2];
			tmpBestMoveCost =

			myData[bestIdx1] = b;
			myData[bestIdx2] = a;

			tmpBestMoveCost = CostPosition[bestIdx1*N+bestIdx2];
			if (CostValueType)  
			{
				tmpBestMoveCost += CostValue[(a-1)*N+b-1];
			}
			price+=tmpBestMoveCost;

			myPair pair;
			pair.a = bestIdx1+1;
			pair.b = bestIdx2+1;
			tempResult.push_back(pair);
			printf("%d %d\n",bestIdx1+1, bestIdx2+1);
		}

   }while(mixed);

   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);


//best move by max distance
   price = 0;
   totalSwaps = 0;
   memcpy(myData,myDataOrg, N*sizeof(short));   
   mixed = false;
   do
   {
	   mixed = false;
	   int bestIdx1 = -1;
	   int bestIdx2 = -1;
	   long tmpBestMoveCost = 0;
	   for (i = 0; i < N; i++)
	   {
		   a = i+1; 
		   if (myData[i] == a)  continue; //ok
		   mixed = true;
		
		   for(j=0; j<N; j++)
		   {
			   if (myData[j] == a) 
			   {
				   short moveDistance = abs(j-i);
				   if (moveDistance>tmpBestMoveCost)
				   {
					   tmpBestMoveCost = moveDistance;
					   bestIdx1 = i;
					   bestIdx2 = j;
				   } else if (moveDistance==tmpBestMoveCost)
				   {
						if (bestIdx1+bestIdx2 < i+j)
						{
							bestIdx1 = i;
							bestIdx2 = j;
						}
				   }
			   }
		   }
	   }

		if (mixed)
		{
			totalSwaps++;
			a = myData[bestIdx1];
			b = myData[bestIdx2];
			tmpBestMoveCost =

			myData[bestIdx1] = b;
			myData[bestIdx2] = a;

			tmpBestMoveCost = CostPosition[bestIdx1*N+bestIdx2];
			if (CostValueType)  
			{
				tmpBestMoveCost += CostValue[(a-1)*N+b-1];
			}
			price+=tmpBestMoveCost;

			myPair pair;
			pair.a = bestIdx1+1;
			pair.b = bestIdx2+1;
			tempResult.push_back(pair);
			printf("%d %d\n",bestIdx1+1, bestIdx2+1);
		}

   }while(mixed);

   checkResult(price);
   printf("Price: %d(%d)\n",price, totalSwaps);

   saveResult();

   return true;
}


int _tmain(int argc, _TCHAR* argv[])
{
	loadInput("sorting.in");
	return 0;
}