#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define BLOCKSU 51 //ブロック数
#define NODESU (BLOCKSU*2-1) //ノード数
#define HEN_MAX 10 //１辺の最大の長さ
#define X_MAX 40 //横の最大値
#define Y_MAX 30 //縦の最大値
#define Z_MAX 30 //高さの最大値

int goukei;

typedef struct _node {
	int info1,info2,info3,info4, info5,info6,info7;
	struct _node *left, *right,*oya;
}Node;
  
//info1が「1のとき横に配列」「2のとき縦に配列」「3のとき上に配列」「4のときはブロック」
//info2は荷台につめる順番
//info3,info4,info5はブロックの横、縦、高さ（info1!=4のときは全て0）
//info6は根を含む右端のノードのinfo1が1,2,3の時1、それ以外は0(全て１)

static Node 

Z={ 0,0,0,0,0,0,0,&Z,&Z,NULL},

YYyy={ 4,51,3,3,4,0,101,&Z,&Z},
YYy={ 4,50,2,3,5,0,100,&Z,&Z},
YY={ 1,0,0,0,0,0,99,&YYyy,&YYy},
XXx={ 4,49,3,3,2,0,98,&Z,&Z},
XX={ 1,0,0,0,0,0,97,&YY,&XXx},
WWw={ 4,48,4,4,2,0,96,&Z,&Z},
WW={ 1,0,0,0,0,0,95,&XX,&WWw},
VVv={ 4,47,3,4,3,0,94,&Z,&Z},
VV={ 1,0,0,0,0,0,93,&WW,&VVv},
UUu={ 4,46,4,3,3,0,92,&Z,&Z},
UU={ 1,0,0,0,0,0,91,&VV,&UUu},
TTt={ 4,45,3,2,3,0,90,&Z,&Z},
TT={ 1,0,0,0,0,0,89,&UU,&TTt},
SSs={ 4,44,3,3,2,0,88,&Z,&Z},
SS={ 1,0,0,0,0,0,87,&TT,&SSs},
RRr={ 4,43,20,20,2,0,86,&Z,&Z},
RR={ 1,0,0,0,0,0,85,&SS,&RRr},
QQq={ 4,42,10,30,20,0,84,&Z,&Z},
QQ={ 1,0,0,0,0,0,83,&RR,&QQq},
PPp={ 4,41,4,1,4,0,82,&Z,&Z},
PP={ 1,0,0,0,0,0,81,&QQ,&PPp},
OOo={ 4,40,2,4,4,0,80,&Z,&Z},
OO={ 1,0,0,0,0,0,79,&PP,&OOo},
NNn={ 4,39,4,2,1,0,78,&Z,&Z},
NN={ 1,0,0,0,0,0,77,&OO,&NNn},
MMm={ 4,38,5,3,2,0,76,&Z,&Z},
MM={ 1,0,0,0,0,0,75,&NN,&MMm},
LLl={ 4,37,1,3,4,0,74,&Z,&Z},
LL={ 1,0,0,0,0,0,73,&MM,&LLl},
KKk={ 4,36,4,3,2,0,72,&Z,&Z},
KK={ 1,0,0,0,0,0,71,&LL,&KKk},
JJj={ 4,35,5,3,2,0,70,&Z,&Z},
JJ={ 1,0,0,0,0,0,69,&KK,&JJj},
IIi={ 4,34,10,10,10,0,68,&Z,&Z},
II={ 1,0,0,0,0,0,67,&JJ,&IIi},
HHh={ 4,33,10,10,10,0,66,&Z,&Z},
HH={ 1,0,0,0,0,0,65,&II,&HHh},
GGg={ 4,32,40,20,10,0,64,&Z,&Z},
GG={ 1,0,0,0,0,0,63,&HH,&GGg},
FFf={ 4,31,50,30,20,0,62,&Z,&Z},
FF={ 1,0,0,0,0,0,61,&GG,&FFf},
EEe={ 4,30,10,10,10,0,60,&Z,&Z},
EE={ 1,0,0,0,0,0,59,&FF,&EEe},
DDd={ 4,29,10,10,10,0,58,&Z,&Z},
DD={ 1,0,0,0,0,0,57,&EE,&DDd},
CCc={ 4,28,10,10,10,0,56,&Z,&Z},
CC={ 1,0,0,0,0,0,55,&DD,&CCc},
BBb={ 4,27,10,10,10,0,54,&Z,&Z},
BB={ 1,0,0,0,0,0,53,&CC,&BBb},
AAa={ 4,26,10,10,10,0,52,&Z,&Z},
AA={ 1,0,0,0,0,0,51,&BB,&AAa},
Yy={ 4,25,10,10,10,0,50,&Z,&Z},
Y={ 1,0,0,0,0,0,49,&AA,&Yy},
Xx={ 4,24,20,20,20,0,48,&Z,&Z},
X={ 1,0,0,0,0,0,47,&Y,&Xx},
Ww={ 4,23,50,5,30,0,46,&Z,&Z},
W={ 1,0,0,0,0,0,45,&X,&Ww},
Vv={ 4,22,20,20,20,0,44,&Z,&Z},
V={ 1,0,0,0,0,0,43,&W,&Vv},
Uu={ 4,21,20,20,20,0,42,&Z,&Z},
U={ 1,0,0,0,0,0,41,&V,&Uu},
Tt={ 4,20,10,10,10,0,40,&Z,&Z},
T={ 1,0,0,0,0,0,39,&U,&Tt},
Ss={ 4,19,50,50,50,0,38,&Z,&Z},
S={ 1,0,0,0,0,0,37,&T,&Ss},
Rr={ 4,18,3,10,50,0,36,&Z,&Z},
R={ 1,0,0,0,0,0,35,&S,&Rr},
Qq={ 4,17,60,40,30,0,34,&Z,&Z},
Q={ 1,0,0,0,0,0,33,&R,&Qq},
Pp={ 4,16,70,30,20,0,32,&Z,&Z},
P={ 1,0,0,0,0,0,31,&Q,&Pp},
Oo={ 4,15,60,2,5,0,30,&Z,&Z},
O={ 1,0,0,0,0,0,29,&P,&Oo},
Nn={ 4,14,6,6,6,0,28,&Z,&Z},
N={ 1,0,0,0,0,0,27,&O,&Nn},
Mm={ 4,13,2,2,4,0,26,&Z,&Z},
M={ 1,0,0,0,0,0,25,&N,&Mm},
Ll={ 4,12,1,2,3,0,24,&Z,&Z},
L={ 1,0,0,0,0,0,23,&M,&Ll},
Kk={ 4,11,5,6,7,0,22,&Z,&Z},
K={ 1,0,0,0,0,0,21,&L,&Kk},
Jj={ 4,10,9,4,7,0,20,&Z,&Z},
J={ 1,0,0,0,0,0,19,&K,&Jj},
Ii={ 4,9,12,3,4,0,18,&Z,&Z},
I={ 1,0,0,0,0,0,17,&J,&Ii},
Hh={ 4,8,8,8,4,0,16,&Z,&Z},
H={ 1,0,0,0,0,0,15,&I,&Hh},
Gg={ 4,7,2,3,4,0,14,&Z,&Z},
G={ 1,0,0,0,0,0,13,&H,&Gg},
Ff={ 4,6,7,7,40,0,12,&Z,&Z},
F={ 1,0,0,0,0,0,11,&G,&Ff},
Ee={ 4,5,10,10,10,0,10,&Z,&Z},
E={ 1,0,0,0,0,0,9,&F,&Ee},
Dd={ 4,4,10,10,10,0,8,&Z,&Z},
D={ 1,0,0,0,0,0,7,&E,&Dd},
Cc={ 4,3,10,10,10,0,6,&Z,&Z},
C={ 1,0,0,0,0,0,5,&D,&Cc},
Bb={ 4,2,30,3,4,0,4,&Z,&Z},
B={ 1,0,0,0,0,0,3,&C,&Bb},
Aa={ 4,1,5,3,2,1,2,&Z,&Z},
A={ 1,0,0,0,0,1,1,&B,&Aa,&Z};

Node *Clone(Node *t1){
	Node *node = malloc(sizeof(Node));
	Copy(node, t1);
	return node;
}

Copy(Node *node,Node *t1){

	
	node->info1 = t1->info1;
	node->info2 = t1->info2;
	node->info3 = t1->info3;
	node->info4 = t1->info4;
	node->info5 = t1->info5;
	node->info6 = t1->info6;
	node->info7 = t1->info7;
	
	if(!node->info1==0){
		node->left=malloc(sizeof(Node));
		Copy(node->left,t1->left);
		node->right=malloc(sizeof(Node));
		Copy(node->right,t1->right);
		node->left->oya=node;
		node->right->oya=node;
	}
	return 0;
}



/*後順走査のよって全体の体積を算出*/
static Node taisekikeisan(Node *t1){


	if((t1->info1>0)&&(t1->info1<4)){
		Node *a1,*b1;
		
		taisekikeisan(a1=t1->left);
		taisekikeisan(b1=t1->right);
		/*横に配置　info3は足し算、info4,info5は大きいほうを選択*/
		if(t1->info1==1){
			t1->info3=a1->info3+b1->info3;
			
			if(a1->info4>b1->info4){
				t1->info4=a1->info4;
			}
			else t1->info4=b1->info4;
			
			if(a1->info5>b1->info5){
				t1->info5=a1->info5;
			}
			else t1->info5=b1->info5;
		
		}	

		/*縦に配置　info4は足し算、info3,info5は大きいほうを選択*/
 		else if(t1->info1==2){
			if(a1->info3>b1->info3){
				t1->info3=a1->info3;
			}
			else t1->info3=b1->info3;
			
			t1->info4=a1->info4+b1->info4;
			
			
			if(a1->info5>b1->info5){
				t1->info5=a1->info5;
			}
			else t1->info5=b1->info5;
		}

		/*上下に配置　info5は足し算、info3,info4は大きいほうを選択*/
		else if(t1->info1==3){
			if(a1->info3>b1->info3){
				
				t1->info3=a1->info3;
			}
			else t1->info3=b1->info3;
			
			if(a1->info4>b1->info4){
				t1->info4=a1->info4;
			}
			else t1->info4=b1->info4;
			
			t1->info5=a1->info5+b1->info5;
		}		
 	//	printf("info1=%2d, info2=%2d, x=%2d, y=%2d, z=%2d \n",  t1->info1,t1->info2, t1->info3,t1->info4,t1->info5);
 		return *t1;
 	}
 	
 	else{
	//	printf("info1=%2d, info2=%2d, x=%2d, y=%2d, z=%2d \n",  t1->info1,t1->info2, t1->info3,t1->info4,t1->info5);
 		return *t1;
 	}
}

//ノードの数字より小さい数字をカウント
static int countChildNodeYoritiisai(Node *target, int value)
{
	int sum=0;
	if(target->info1==0)return 0;
	
	
	if((target->info1==4)&&(target->info2<value)){
		sum=1;

	}

	sum+=countChildNodeYoritiisai(target->left,value);
	sum+=countChildNodeYoritiisai(target->right,value);

	return sum;
	
}


static int mudaNode(Node *target, int value)
{
	int count=0;
	while(target->info6!=1){
		
		
	 
		
		
		if((target->oya->info1!=2)&&(target->oya->right!=target)){
			count+=countChildNodeYoritiisai(target->oya->right,value);
		}
		target=target->oya;
		
	/*	if (target->oya == NULL) { 
		printf("!!!!!!!!!!"); 
		exit(1); 
		}
		
		*/
	}
	return count;
}

//先順走査によって無駄の合計値を算出
//int goukei=0;
static Node preorder(Node *t1){
	if((t1->info1>0)&&(t1->info1<4)){
		Node *a1,*b1;
 	
		t1->left->oya = t1;
		t1->right->oya = t1;
		preorder(a1=t1->left);
		preorder(b1=t1->right);
	return *t1;	
	}
	else{
		goukei+=mudaNode(t1,t1->info2);
		
		return *t1;
 	}
}

//親子関係にあれば１を返す、なければ０
static int isOyakokankei(Node *t1,Node *t2){
	Node *n;
	
	n = t1;
	while(n!=&Z){
		n=n->oya;
		if(n==t2)return 1;
	}
	n = t2;
	while(n!=&Z){
		n=n->oya;
		if(n==t1)return 1;
	}
	return 0;
}

//ランダムでノードを探索
static Node *findNode(int ransu, Node *t1){
	Node *a1,*b1;
	
	if(t1!=&Z){
		
		if(t1->info7==ransu)return t1;

		a1 = findNode(ransu,t1->left);
		b1 = findNode(ransu,t1->right);
		
		if(a1!=&Z) return a1;
		else if(b1!=&Z)return b1;
        

	}
	return &Z;
}


//部分木の交換
static void ChangeSubTree(Node *t1,Node *t2){
	Node a1,b1,*c1,*n;

	if(t1->oya == t2->oya){
		c1 = t1->oya->left;
		t1->oya->left = t1->oya->right;
		t1->oya->right = c1;
	}
	else{
		if(t1->oya->left==t1)t1->oya->left=t2;
		else t1->oya->right=t2;

		if(t2->oya->left==t2)t2->oya->left=t1;
		else t2->oya->right=t1;
	}


	a1.info6=t1->info6;
	a1.oya=t1->oya;
	b1.info6=t2->info6;
	b1.oya=t2->oya;

	t1->info6=b1.info6;
	t1->oya=b1.oya;
	t2->info6=a1.info6;
	t2->oya=a1.oya;

	if(t1->info6){
		n = t1;
		while(n->info1!=4){
			n->right->info6=1;
			n=n->right;
		}
		
		n = t2;
		while(n->info1!=4){
			n->right->info6=0;
			n=n->right;
		}
	}

	else if(t2->info6){
		n = t2;
		while(n->info1!=4){
			n->right->info6=1;
			n=n->right;
		}
		
		n = t1;
		while(n->info1!=4){
			n->right->info6=0;
			n=n->right;
		}
	}
	return;
}

//ランダムで部分木を交換
int ransu1,ransu2;
static Node RandomChangeSubTree(){

	Node *targetNode1, *targetNode2;
	ransu1 = rand()%NODESU;
	ransu2 = (ransu1+1+(rand()%(NODESU-1)))%NODESU;

	
	targetNode1 = findNode(ransu1,&A);
	targetNode2 = findNode(ransu2,&A);

	if(!isOyakokankei(targetNode1,targetNode2))
		ChangeSubTree(targetNode1,targetNode2);
	
	return *targetNode1, *targetNode2;
}

//ランダムで選択したブロックを９０度回転
static Node Kaiten(Node *t1){
	int a1,b1;

	do{
		ransu1 = rand()%NODESU;
		t1 = findNode(ransu1,&A);
	}while(t1->info1!=4);
		
	a1=t1->info3;
	b1=t1->info4;
	t1->info3=b1;
	t1->info4=a1;
 	
	return *t1;
}

//ランダムで選択したノードの配置変換
static Node HaitiTenkan(Node *t1){
	
	do{
		ransu1 = rand()%NODESU;
		t1 = findNode(ransu1,&A);
	}while((t1->info1== 0)||(t1->info1==4));

	ransu2 = rand()%2;
	
	if(ransu2){
		if(t1->info1==1)
			t1->info1=2;
		else if(t1->info1==2)
			t1->info1=3;
		else t1->info1=1;
 	}

	else {
		if(t1->info1==1)
			t1->info1=3;
		else if(t1->info1==2)
			t1->info1=1;
		else t1->info1=2;
 	}
	return *t1;
}

	
/*----------------------------------------------------------------------------*/
int main()
{
	int i1,ransu_R,kai_x,kai_y,kai_z,sairyokai_x,sairyokai_y,sairyokai_z,saisho_taiseki,sairyo_taiseki,x_hyoka=1000000,x_hyoka_ima;
	int pena_x,pena_y,pena_z,kai_muda=1000000,kai_muda_ima;
	double shokiondo = 0.999,ransu_SA;
	double ondo = shokiondo;
	double reikyakuritu = 0.99;
	Node *temp = &A;
	Node *copy1 = Clone(&A);
	Node *copy2 = Clone(&A);
	Node *copy3 = Clone(&A);
	Node *copy4 = Clone(&A);


	
	srand((unsigned) time(NULL));
	//初期解生成
	
	Aa.info3=rand()%HEN_MAX+1;Aa.info4=rand()%HEN_MAX+1;Aa.info5=rand()%HEN_MAX+1;
	Bb.info3=rand()%HEN_MAX+1;Bb.info4=rand()%HEN_MAX+1;Bb.info5=rand()%HEN_MAX+1;
	Cc.info3=rand()%HEN_MAX+1;Cc.info4=rand()%HEN_MAX+1;Cc.info5=rand()%HEN_MAX+1;
	Dd.info3=rand()%HEN_MAX+1;Dd.info4=rand()%HEN_MAX+1;Dd.info5=rand()%HEN_MAX+1;
	Ee.info3=rand()%HEN_MAX+1;Ee.info4=rand()%HEN_MAX+1;Ee.info5=rand()%HEN_MAX+1;
	Ff.info3=rand()%HEN_MAX+1;Ff.info4=rand()%HEN_MAX+1;Ff.info5=rand()%HEN_MAX+1;
	Gg.info3=rand()%HEN_MAX+1;Gg.info4=rand()%HEN_MAX+1;Gg.info5=rand()%HEN_MAX+1;
	Hh.info3=rand()%HEN_MAX+1;Hh.info4=rand()%HEN_MAX+1;Hh.info5=rand()%HEN_MAX+1;
	Ii.info3=rand()%HEN_MAX+1;Ii.info4=rand()%HEN_MAX+1;Ii.info5=rand()%HEN_MAX+1;
	Jj.info3=rand()%HEN_MAX+1;Jj.info4=rand()%HEN_MAX+1;Jj.info5=rand()%HEN_MAX+1;
	Kk.info3=rand()%HEN_MAX+1;Kk.info4=rand()%HEN_MAX+1;Kk.info5=rand()%HEN_MAX+1;
	Ll.info3=rand()%HEN_MAX+1;Ll.info4=rand()%HEN_MAX+1;Ll.info5=rand()%HEN_MAX+1;
	Mm.info3=rand()%HEN_MAX+1;Mm.info4=rand()%HEN_MAX+1;Mm.info5=rand()%HEN_MAX+1;
	Nn.info3=rand()%HEN_MAX+1;Nn.info4=rand()%HEN_MAX+1;Nn.info5=rand()%HEN_MAX+1;
	Oo.info3=rand()%HEN_MAX+1;Oo.info4=rand()%HEN_MAX+1;Oo.info5=rand()%HEN_MAX+1;
	Pp.info3=rand()%HEN_MAX+1;Pp.info4=rand()%HEN_MAX+1;Pp.info5=rand()%HEN_MAX+1;
	Qq.info3=rand()%HEN_MAX+1;Qq.info4=rand()%HEN_MAX+1;Qq.info5=rand()%HEN_MAX+1;
	Rr.info3=rand()%HEN_MAX+1;Rr.info4=rand()%HEN_MAX+1;Rr.info5=rand()%HEN_MAX+1;
	Ss.info3=rand()%HEN_MAX+1;Ss.info4=rand()%HEN_MAX+1;Ss.info5=rand()%HEN_MAX+1;
	Tt.info3=rand()%HEN_MAX+1;Tt.info4=rand()%HEN_MAX+1;Tt.info5=rand()%HEN_MAX+1;
	Uu.info3=rand()%HEN_MAX+1;Uu.info4=rand()%HEN_MAX+1;Uu.info5=rand()%HEN_MAX+1;
	Vv.info3=rand()%HEN_MAX+1;Vv.info4=rand()%HEN_MAX+1;Vv.info5=rand()%HEN_MAX+1;
	Ww.info3=rand()%HEN_MAX+1;Ww.info4=rand()%HEN_MAX+1;Ww.info5=rand()%HEN_MAX+1;
	Xx.info3=rand()%HEN_MAX+1;Xx.info4=rand()%HEN_MAX+1;Xx.info5=rand()%HEN_MAX+1;
	Yy.info3=rand()%HEN_MAX+1;Yy.info4=rand()%HEN_MAX+1;Yy.info5=rand()%HEN_MAX+1;
	AAa.info3=rand()%HEN_MAX+1;AAa.info4=rand()%HEN_MAX+1;AAa.info5=rand()%HEN_MAX+1;
	BBb.info3=rand()%HEN_MAX+1;BBb.info4=rand()%HEN_MAX+1;BBb.info5=rand()%HEN_MAX+1;
	CCc.info3=rand()%HEN_MAX+1;CCc.info4=rand()%HEN_MAX+1;CCc.info5=rand()%HEN_MAX+1;
	DDd.info3=rand()%HEN_MAX+1;DDd.info4=rand()%HEN_MAX+1;DDd.info5=rand()%HEN_MAX+1;
	EEe.info3=rand()%HEN_MAX+1;EEe.info4=rand()%HEN_MAX+1;EEe.info5=rand()%HEN_MAX+1;
	FFf.info3=rand()%HEN_MAX+1;FFf.info4=rand()%HEN_MAX+1;FFf.info5=rand()%HEN_MAX+1;
	GGg.info3=rand()%HEN_MAX+1;GGg.info4=rand()%HEN_MAX+1;GGg.info5=rand()%HEN_MAX+1;
	HHh.info3=rand()%HEN_MAX+1;HHh.info4=rand()%HEN_MAX+1;HHh.info5=rand()%HEN_MAX+1;
	IIi.info3=rand()%HEN_MAX+1;IIi.info4=rand()%HEN_MAX+1;IIi.info5=rand()%HEN_MAX+1;
	JJj.info3=rand()%HEN_MAX+1;JJj.info4=rand()%HEN_MAX+1;JJj.info5=rand()%HEN_MAX+1;
	KKk.info3=rand()%HEN_MAX+1;KKk.info4=rand()%HEN_MAX+1;KKk.info5=rand()%HEN_MAX+1;
	LLl.info3=rand()%HEN_MAX+1;LLl.info4=rand()%HEN_MAX+1;LLl.info5=rand()%HEN_MAX+1;
	MMm.info3=rand()%HEN_MAX+1;MMm.info4=rand()%HEN_MAX+1;MMm.info5=rand()%HEN_MAX+1;
	NNn.info3=rand()%HEN_MAX+1;NNn.info4=rand()%HEN_MAX+1;NNn.info5=rand()%HEN_MAX+1;
	OOo.info3=rand()%HEN_MAX+1;OOo.info4=rand()%HEN_MAX+1;OOo.info5=rand()%HEN_MAX+1;
	PPp.info3=rand()%HEN_MAX+1;PPp.info4=rand()%HEN_MAX+1;PPp.info5=rand()%HEN_MAX+1;
	QQq.info3=rand()%HEN_MAX+1;QQq.info4=rand()%HEN_MAX+1;QQq.info5=rand()%HEN_MAX+1;
	RRr.info3=rand()%HEN_MAX+1;RRr.info4=rand()%HEN_MAX+1;RRr.info5=rand()%HEN_MAX+1;
	SSs.info3=rand()%HEN_MAX+1;SSs.info4=rand()%HEN_MAX+1;SSs.info5=rand()%HEN_MAX+1;
	TTt.info3=rand()%HEN_MAX+1;TTt.info4=rand()%HEN_MAX+1;TTt.info5=rand()%HEN_MAX+1;
	UUu.info3=rand()%HEN_MAX+1;UUu.info4=rand()%HEN_MAX+1;UUu.info5=rand()%HEN_MAX+1;
	VVv.info3=rand()%HEN_MAX+1;VVv.info4=rand()%HEN_MAX+1;VVv.info5=rand()%HEN_MAX+1;
	WWw.info3=rand()%HEN_MAX+1;WWw.info4=rand()%HEN_MAX+1;WWw.info5=rand()%HEN_MAX+1;
	XXx.info3=rand()%HEN_MAX+1;XXx.info4=rand()%HEN_MAX+1;XXx.info5=rand()%HEN_MAX+1;
	YYy.info3=rand()%HEN_MAX+1;YYy.info4=rand()%HEN_MAX+1;YYy.info5=rand()%HEN_MAX+1;
	YYyy.info3=rand()%HEN_MAX+1;YYyy.info4=rand()%HEN_MAX+1;YYyy.info5=rand()%HEN_MAX+1;
	
	saisho_taiseki = Aa.info3*Aa.info4*Aa.info5+Bb.info3*Bb.info4*Bb.info5+Cc.info3*Cc.info4*Cc.info5+
		Dd.info3*Dd.info4*Dd.info5+Ee.info3*Ee.info4*Ee.info5+Ff.info3*Ff.info4*Ff.info5+
		Gg.info3*Gg.info4*Gg.info5+Hh.info3*Hh.info4*Hh.info5+Ii.info3*Ii.info4*Ii.info5+
		Jj.info3*Jj.info4*Jj.info5+Kk.info3*Kk.info4*Kk.info5+Ll.info3*Ll.info4*Ll.info5+
		Mm.info3*Mm.info4*Mm.info5+Nn.info3*Nn.info4*Nn.info5+Oo.info3*Oo.info4*Oo.info5+
		Pp.info3*Pp.info4*Pp.info5+Qq.info3*Qq.info4*Qq.info5+Rr.info3*Rr.info4*Rr.info5+
		Ss.info3*Ss.info4*Ss.info5+Tt.info3*Tt.info4*Tt.info5+Uu.info3*Uu.info4*Uu.info5+
		Vv.info3*Vv.info4*Vv.info5+Ww.info3*Ww.info4*Ww.info5+Xx.info3*Xx.info4*Xx.info5+
		Yy.info3*Yy.info4*Yy.info5+AAa.info3*AAa.info4*AAa.info5+BBb.info3*BBb.info4*BBb.info5+
		CCc.info3*CCc.info4*CCc.info5+DDd.info3*DDd.info4*DDd.info5+EEe.info3*EEe.info4*EEe.info5+
		FFf.info3*FFf.info4*FFf.info5+GGg.info3*GGg.info4*GGg.info5+HHh.info3*HHh.info4*HHh.info5+
		IIi.info3*IIi.info4*IIi.info5+JJj.info3*JJj.info4*JJj.info5+KKk.info3*KKk.info4*KKk.info5+
		LLl.info3*LLl.info4*LLl.info5+MMm.info3*MMm.info4*MMm.info5+NNn.info3*NNn.info4*NNn.info5+
		OOo.info3*OOo.info4*OOo.info5+PPp.info3*PPp.info4*PPp.info5+QQq.info3*QQq.info4*QQq.info5+
		RRr.info3*RRr.info4*RRr.info5+SSs.info3*SSs.info4*SSs.info5+TTt.info3*TTt.info4*TTt.info5+
		UUu.info3*UUu.info4*UUu.info5+VVv.info3*VVv.info4*VVv.info5+WWw.info3*WWw.info4*WWw.info5+
		XXx.info3*XXx.info4*XXx.info5+YYy.info3*YYy.info4*YYy.info5+YYyy.info3*YYyy.info4*YYyy.info5;
		
	printf("-----------------------------------------------------------------------------------------\n");
	printf("体積は%d\n",saisho_taiseki);
	printf("パッキング率は%2f\n\n\n",((float)saisho_taiseki/(X_MAX*Y_MAX*Z_MAX))*100);
	goukei = 0;
	preorder(temp);
	printf("初期の無駄合計は%d\n",goukei);
	taisekikeisan(temp);
	printf("初期のx＝%2d,y=%2d,z=%2d\n\n",temp->info3,temp->info4,temp->info5);
	
	
	



//取り出し順序を考慮しない最初のＳＡ
printf("---------最初のＳＡ---------------\n\n");


		for(i1=0;i1<100;i1++){
			
			//ransu_Rは０から９９
			ransu_R = rand()%100;
			
			//部分木入れ替え
			if((0<=ransu_R) && (ransu_R<35)){
			
			RandomChangeSubTree();
			preorder(temp);
			//printf("無駄合計は%d\n",goukei);
			taisekikeisan(temp);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}

			//ブロック回転
			else if((35<=ransu_R) && (ransu_R<70)){
			
			Kaiten(temp);
			preorder(temp);
			//printf("無駄合計は%d\n",goukei);
			taisekikeisan(temp);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}
			
			//配置転換
			else {
			
			HaitiTenkan(temp);
			preorder(temp);
			//printf("無駄合計は%d\n",goukei);
			taisekikeisan(temp);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}
			
			kai_x=temp->info3;
			kai_y=temp->info4;
			kai_z=temp->info5;
		
			//x軸でのはみ出しのペナルティ
			if(kai_x>X_MAX)
				pena_x=0;//*(i1+1);
			else
				pena_x=0;
			

			//y軸でのはみ出しのペナルティ
			if(kai_y>Y_MAX)
				pena_y=(kai_y-Y_MAX)*1000;//*(i1+1);
			else
				pena_y=0;
			

			//z軸でのはみ出しのペナルティ
			if(kai_z>Z_MAX)
				pena_z=(kai_z-Z_MAX)*1000;//*(i1+1);
			else
				pena_z=0;
			
			x_hyoka_ima=kai_x+pena_y+pena_z;
			//ペナルティの合計値を表示
			//printf("ペナ合計は　　　　　　　　　　　　　　　　　　　　　　%f\n",pena_x+pena_y+pena_z);
			
		
			//printf("%d　　",taiseki_ima);
			//0から1までの値を設定
			ransu_SA = rand()/RAND_MAX;
			
			//前回より解がよかったら（評価値が小さかったら）
			if(x_hyoka_ima<x_hyoka){
					x_hyoka = x_hyoka_ima;
					sairyokai_x=kai_x;
					sairyokai_y=kai_y;
					sairyokai_z=kai_z;
					copy1 = Clone(&A);
					//copy2を参照すれば最良解の形がわかるはず
					copy2 = Clone(copy1);
			
			}
			
			//前回より解が悪かったら（評価値が大きかったら）
			else if(ransu_SA<ondo){
			//この時移動する
			//	kai_muda = kai_muda_ima;
				copy1 = Clone(&A);
			}

			
			else{
			//この時移動しない
				Node *A= Clone(copy1);
			}
			//数値の初期化
			pena_x=0;
			pena_y=0;
			pena_z=0;
			
			ondo = ondo*reikyakuritu;
			
			goukei = 0;
			
		
		}
		printf("終了温度は%f\n",ondo);
		printf("評価値は　　　　　　　　　　　　　　　　　　　　　　　%d\n\n\n",x_hyoka);
	
		printf("最良の時：ｘ＝%2d、ｙ＝%2d、ｚ＝%2d\n\n",sairyokai_x,sairyokai_y,sairyokai_z);
		
		sairyo_taiseki=sairyokai_x*sairyokai_y*sairyokai_z;
		printf("最良体積は%2d\n",sairyo_taiseki);
		//printf("パッキング率は%2f\n\n\n",((float)saisho_taiseki/sairyo_taiseki)*100);
		
		ondo = shokiondo;
		
	
	preorder(&A);
	printf("最初のＳＡ終了時の無駄合計は%d\n",goukei);




	goukei=0;

//取り出し順序も考慮したＳＡ
printf("---------次のＳＡ---------------\n\n");

copy3=Clone(copy2);
copy4=Clone(copy2);


	//部分木：回転：配置転換＝７：１：２で３パターンから選ぶ
	for(i1=0;i1<10;i1++){
			
			//ransu_Rは０から９９
			ransu_R = rand()%100;
			
			//部分木入れ替え
			if((0<=ransu_R) && (ransu_R<35)){
			RandomChangeSubTree();
			preorder(copy2);
			printf("入替無駄合計は%d\n",goukei);
			taisekikeisan(copy2);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}

			//部分回転
			else if((35<=ransu_R) && (ransu_R<70)){
			Kaiten(copy2);
			preorder(copy2);
			printf("回転無駄合計は%d\n",goukei);
			taisekikeisan(copy2);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}
			
			//配置転換
			else {
			HaitiTenkan(copy2);
			preorder(copy2);
			printf("配置無駄合計は%d\n",goukei);
			taisekikeisan(copy2);
			//printf("x＝%2d,y=%2d,z=%2d\n",temp->info3,temp->info4,temp->info5);
			}
			
			kai_x=copy2->info3;
			kai_y=copy2->info4;
			kai_z=copy2->info5;
			//printf("かいＺは%d\n",kai_z);

			//x軸でのはみ出しのペナルティ
			if(kai_x>X_MAX)
				pena_x=(kai_x-X_MAX)*100;//*(i1+1);
			else
				pena_x=0;
			

			//y軸でのはみ出しのペナルティ
			if(kai_y>Y_MAX)
				pena_y=(kai_y-Y_MAX)*100;//*(i1+1);
			else
				pena_y=0;
			

			//z軸でのはみ出しのペナルティ
			if(kai_z>Z_MAX)
				pena_z=(kai_z-Z_MAX)*100;//*(i1+1);
			else
				pena_z=0;
			
			
			//ペナルティの合計値を表示
			//printf("ペナ合計は　　　　　　　　　　　　　　　　　　　　　　%f\n",pena_x+pena_y+pena_z);
			
			//現在の解無駄
			kai_muda_ima=goukei+pena_x+pena_y+pena_z;
			
			printf("合計は%d　ペナｘは%d　ペナｙは%d　ペナｚは%d\n",goukei,pena_x,pena_y,pena_z);
			printf("解無駄今は%d\n",kai_muda_ima);
			//printf("無駄合計とペナをあわせた途中の評価値　　　　　　　　　%f\n\n",kai_muda_ima);
			
			
			
			//0から1までの値を設定
			ransu_SA = rand()/RAND_MAX;
			
			//前回より解がよかったら（評価値が小さかったら）
			if(kai_muda_ima<kai_muda){
					kai_muda = kai_muda_ima;
					sairyokai_x=kai_x;
					sairyokai_y=kai_y;
					sairyokai_z=kai_z;
					copy3 = Clone(copy2);
					//copy4を参照すれば最良解の形がわかるはず
					copy4 = Clone(copy3);
			
			}
			
			//前回より解が悪かったら（評価値が大きかったら）
			else if(ransu_SA<ondo){
			
				copy3 = Clone(copy2);
			}

			
			else{
				copy2= Clone(copy3);
			}
			//数値の初期化
			goukei=0;
			pena_x=0;
			pena_y=0;
			pena_z=0;
			
			ondo = ondo*reikyakuritu;
			
		
		}
		printf("終了温度は%f\n",ondo);
		printf("評価値は　　　　　　　　　　　　　　　　　　　　　　　%d\n\n\n",kai_muda);
	
		printf("最良の時：ｘ＝%2d、ｙ＝%2d、ｚ＝%2d\n\n",sairyokai_x,sairyokai_y,sairyokai_z);
		
		sairyo_taiseki=sairyokai_x*sairyokai_y*sairyokai_z;
		printf("最良体積は%2d\n",sairyo_taiseki);
		//printf("パッキング率は%2f",((float)saisho_taiseki/sairyo_taiseki)*100);
	
	
	
	return 0;
}