#include <iostream>
#include <stdlib.h>
#include <stdio.h>
//#include <conio.h>

#define MAX_N 5000
#define MAX_L 5000

int Fcelu(int n,long el,int (&p)[20],int (&w)[20],int (&d)[20]);


	int otoczenie(int n, long y, long (&X)[MAX_N], int &dlN)
	{
		char t[10]="";  //stala - ilosc zadan
		char tmp;
		char zm[10]="%0"; char tt[2];

		long il=n*(n-1)/2-1;
		int k=dlN;
		int i=0,j=0;

		sprintf(tt,"%d",n);
		strcat(zm,tt); strcat(zm,"d");


		for (i=0; i<=il; i++)
		{
			for (j=(i+1); j<=n-1; j++)
			{
				//printf("dupa i=%d j=%d k=%d il=%d\n",i,j,k,il);
				sprintf(t,zm,(int)y);
				tmp=t[i];
				t[i]=t[j];
				t[j]=(char)tmp;
				X[k]=atoi(t);
				k++;
			}
		}
		dlN=k--;
		return 0;
	}


	int lepszy(long &piBest,long (&X)[MAX_N],int dlN,int n,long el,int (&p)[20],int (&w)[20],int (&d)[20])
	{
		int fpi=0,fpiBest=0;
		for (int i=0; i<dlN; i++)
		{
			fpi=Fcelu(n,X[i],p,w,d);
			fpiBest=Fcelu(n,piBest,p,w,d);
			if (fpi < fpiBest) { piBest=X[i]; return 1;}
		}						
		return 0;
	}
	
	
	int usunN(int k, long (&X)[MAX_N],int dl)
	{
		for (int i=k; i<dl; i++) //i<dl-1 ??
		{
			X[i]=X[i+1];
			//if (i==k) { printf("usuwany:%d",X[i]); }			
		}
		return 0;		
	}


	int Fcelu(int n,long el,int (&p)[20],int (&w)[20],int (&d)[20])
	{
		char t[10]="";
		char zm[10]="%0"; char tt[2];
		sprintf(tt,"%d",n);
		strcat(zm,tt); strcat(zm,"d");
		sprintf(t,zm,(int)el);

		int C=0,T=0,suma=0;
		int k=strlen(t);
		for (int i=0; i<k; i++)
		{
			C=0;
			for (int j=0; j<=i; j++) C+=p[ (t[j]-48) ];
			T=C-d[ t[i]-48 ];
			if (T<0) T=0;
			suma+=T * w[ t[i]-48 ];
			//printf("znak:%c liczba:%d suma:%d  T:%d C:%d p:%d w:%d d:%d\n",t[i],t[i]-48,suma,T,C,p[t[i]-48],w[t[i]-48],d[t[i]-48]);
		}
                //printf("\nFcelu[%d]:%d",el,suma);
                //if (suma < 216) printf("\nNIE DZIAŁA!!!\n");// else printf(".");
		return suma;
	}


	long najlepszy(long (&X)[MAX_N],int n,int (&p)[20],int (&w)[20],int (&d)[20],int dlN)
	{
		int min=100000;
		int fpi;
		long el=0;
		for (int i=0; i<dlN; i++)
		{
			fpi=Fcelu(n,X[i],p,w,d);
			//printf("\nfc[%d]:%d",X[i],fpi);
			if (fpi < min) { min=fpi; el=X[i]; }
		}
		//printf("\nnajlepszy:%d",el);
		return el;
	}


int main(int argc, char* argv[])
{
	int p[20]={2,4,6,8,10,2,4,6,8,10};
	int w[20]={1,5,3,7,9,2,4,6,8,10};
	int d[20]={4,3,5,8,12,4,3,5,8,12};

	int n=atoi(argv[1]); //ilosc elementow

	long pi=0; //aktualna permutacja
	long LTS[MAX_L]; //lista tabu
	long bestPI=0;
	long y;

	long N[MAX_N]; //otoczenie
	int dlN=0;
	int dlLTS=0;

	//LTS[0]=1230; dlLTS=1; //jakis przyklad na liscie tabu, potem usunac !!!

	pi=43210; //rozwiazanie poczatkowe == 021
	bestPI=pi;
        int czy=0;
        for (int i=0; i<100; i++) //zmienic - moze to byc kryterium stopu
	{
		otoczenie(n,pi,N,dlN);
		//printf("Elementy N: %d, %d, %03d\n", N[0],N[1],N[2]);
		for (int j=0; j<dlN; j++)
		 for (int k=0; k<dlLTS; k++)
		 {
		 	if (N[j]==LTS[k] && !lepszy(bestPI,N,dlN,n,pi,p,w,d)) { usunN(j,N,dlN); dlN--; }
		 }

		y=najlepszy(N,n,p,w,d,dlN);
		//printf("\ny:%d  fcelu[y]:%d  bestPI:%d  fcelu[bestPI]:%d",y,Fcelu(n,y,p,w,d),bestPI,Fcelu(n,bestPI,p,w,d));
		if ( Fcelu(n,y,p,w,d) <= Fcelu(n,bestPI,p,w,d) ) bestPI=y;
		pi=y;
		for (int j=0; j<dlLTS; j++)
                        if ( LTS[j]==pi ) czy=1;
                if (czy==0) { LTS[dlLTS]=pi; dlLTS++; }
	}

        char tmp[10];
        char zm[10]="%0"; char tt[2];
        sprintf(tt,"%d",n);
	strcat(zm,tt); strcat(zm,"d");
        sprintf(tmp,zm,bestPI);
//        printf("\nNajlepsza permutacja:");
//	printf(zm, bestPI);
        printf("\nNajlepsza permutacja:");
        for (int i=0; i<n; i++) printf("%c ",tmp[i]+1);
        printf("\nWartosc f-cji celu:%d",Fcelu(n,bestPI,p,w,d));

	//printf("Elementy N: %d, %d, %d\n", N[0],N[1],N[2]);
//        getch();
	scanf("%c",tmp[0]);
	return 0;
}
