#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
const int l=3;			//l-diversity
const int limit=2;		//l-diversity

struct element			//病人的數據結構
{
	int num;
	int gid;
	char name[10];
	int age;
	int zip;
	char disease[20];
	bool flag;
	int bnum;
};
element op[50000];		//舊病人數據
element np[50000];		//新病人數據
int onum;				//舊病人個數
int nnum;				//新病人個數
int remain;				//未被分配的病人個數

struct node				//桶中病人的數據結構
{
	char disease[100];
	int people[5000];
	int pnum;
	int cnum;
};
node SA[10];			//用于記錄等價類中的疾病

node distable[100];		//記錄未被分組的疾病和病人情況
int remain_dis;
int dnum;


struct bucket			//桶的數據結構
{
	bool flag;
	node dis[10];
	int dnum;
	int cnum;
}buc[500];
int bnum;				//桶的個數

struct hash_node		//hash表的數據結構
{
	char disease[100];
	int bnumber;
	bool flag;
}hashtable[10000];

struct hashdis_node		//hash表的數據結構
{
	char disease[20];
	int dnumber;
	bool flag;
}hashdis[10000];

typedef struct t_node	//語義樹的定義
{
	char disease[20];
	struct t_node *father;
}t_node,*tree;
tree root;
struct f_node
{
	char disease[20];
	tree T;
	int height;
}dislist[100];
int disnum=17;
int maxheight=3;

int cnum;				//虛擬元素的個數
int fnum=1;

void input(void);		//讀文件函數
void division(void);	//拆分階段
void balancing(void);	//平衡階段
void assignment(void);	//分配階段
void split(void);		//剝離階段

int hash(int num);			//hash的映射函數
int f(int num);			//hash的key計算函數
int searchhash(int key, char disease[]);		//查找hash表
void inserthash(int key, char disease[], int bnumber);		//插入hash表

int hashdisease(char dis[]);			//hash的映射函數
int searchdis(char dis[]);		//查找hash表
void insertdis(char dis[], int dnumber);		//插入hash表

void create_tree(void);
int caculate(char a[], char b[]);

int caculate_digit(int i, int j);	//計算郵編

int filenum=0;

int main()
{
	
	FILE *fptr;
	char tt[20];
	scanf("%s",tt);
	if((fptr=fopen("500.txt",'r'))==NULL)
		int b;
	
	double m[55][2];
	int i=0;
	while(fscanf(fptr,"%lf %lf", &m[i][0],&m[i][1])!=EOF)
		i++;
	double t1=0;
	double t2=0;

	for(i=0;i<50;i++)
	{
		t1+=(500-m[i][0])/500;
		t2+=m[i][1];
	}
	printf("%.1lf, %.1lf",t1/50,t2/50);
	
	
	
	printf("剩余未分配人員 虛擬元素個數\n");
	create_tree();
	while(fnum!=51)
	{
		input();
		if(onum!=0)
			division();
		balancing();
		assignment();
		split();
		int i,j,k=0;
		printf(" %d %d\n",remain,cnum);
		for(i=0;i<bnum;i++)
		{
			for(j=0;j<buc[i].dnum;j++)
			{
				buc[i].dis[j].cnum=0;
				buc[i].dis[j].pnum=0;
			}
			buc[i].flag=false;
			buc[i].cnum=0;
		}
		bnum=0;
		for(i=0;i<10000;i++)
		{
			hashdis[i].flag=false;
			hashtable[i].flag=false;
			remain=0;
		}
		cnum=0;
		onum=0;
		nnum=0;
		dnum=0;
		remain=0;
		remain_dis=0;
		for(i=0;i<100;i++)
		{
			distable[i].pnum=0;
		}
		for(i=0;i<5000;i++)
			np[i].flag=false;
	}
	return 0;
}
void input(void)
{
	FILE *fptr1;
	FILE *fptr2;
	char old[20];
	char newfile[20];
//	printf("源文件名稱\n");
//	scanf("%s",old);
//	printf("新文件名稱\n");
//	scanf("%s",newfile);
	itoa(fnum,old,10);
	strcat(old,"gg.txt");
	itoa(fnum,newfile,10);
	strcat(newfile,".txt");
	
	int i=0;
//	if((fptr1=fopen("old.txt","r"))==NULL)
	if((fptr1=fopen(old,"r"))==NULL)
		printf("源文件打開失敗/n");
	else
	{
		if ((fptr2=fopen(newfile,"r"))==NULL)
			printf("新文件打開失敗/n");
		else
		{
			while(fscanf(fptr1,"%d %s",&op[i].gid, op[i].name)!=EOF)
			{
				if(strcmp(op[i].name,"c")==0)
					fscanf(fptr1,"%s",op[i].disease);
				else
				{
					fscanf(fptr1,"%d %d %s",&op[i].age, &op[i].zip, op[i].disease);
					op[i].num=++i;
				}
			}
			onum=i;
			i=0;
			while(fscanf(fptr2,"%s %d %d %s",np[i].name,&np[i].age, &np[i].zip, np[i].disease)!=EOF)
				np[i].num=++i;
			nnum=i;
			remain=nnum;
		}
	}
	for(i=0;i<10;i++)
		buc[i].flag=false;
	bnum=0;
}

void division(void)
{
	bool flag=false;
	int i,j,k=0,g,key,save=0,bnumber;
	int tap=1;
	
	bnum=0;
	
	
	for(i=0;i<onum+1;i++)
	{
		if(op[i].gid!=tap||i==onum)
		{
			key=f(k);
			bnumber=searchhash(key, SA[k].disease);
			if(bnumber<0)			//建立新桶
			{
				buc[bnum].dnum=0;
				buc[bnum].cnum=0;
				buc[bnum].flag=false;
				for(g=save;g<i;g++)
				{
					for(j=0;j<nnum;j++)
					{
						if(strcmp(op[g].name,np[j].name)==0)
						{	
							flag=true;
							np[j].flag=true;
							break;
						}
					}
					strcpy(buc[bnum].dis[buc[bnum].dnum].disease,op[g].disease);
					buc[bnum].dis[buc[bnum].dnum].cnum=0;
					buc[bnum].dis[buc[bnum].dnum].pnum=0;
					if(flag==true)
					{
						flag=false;
						buc[bnum].flag=true;
						buc[bnum].dis[buc[bnum].dnum].people[buc[bnum].dis[buc[bnum].dnum].pnum++]=j;
						remain--;
					}
					buc[bnum].dnum++;
				}
				inserthash(key, SA[k].disease, bnum);
				bnum++;
			}
			else							//桶可以合并
			{
				for(g=save;g<i;g++)
				{
					for(j=0;j<nnum;j++)
					{
						if(strcmp(op[g].name,np[j].name)==0)
						{	
							flag=true;
							np[j].flag=true;
							break;
						}
					}
					if(flag==true)
					{
						flag=false;
						for(k=0;k<buc[bnumber].dnum;k++)
						{
							if(strcmp(np[j].disease,buc[bnumber].dis[k].disease)==0)
							{
								buc[bnumber].dis[k].people[buc[bnumber].dis[k].pnum++]=j;
								remain--;
								break;
							}
						}
						
					}
				}
			}
			save=i;
			tap++;
			k=0;
			if(i!=onum)
				strcpy(SA[k++].disease,op[i].disease);
		}
		else
			strcpy(SA[k++].disease,op[i].disease);
	}
}
void balancing(void)
{
	int i,j,k,result,max=0,tmp,bnumber;
	bool flag=false;
	for(i=0;i<nnum;i++)						//將新病人沒有分配過的元素按照疾病分類
	{
		if(np[i].flag==false)
		{
			result=searchdis(np[i].disease);
			if(result<0)
			{
				strcpy(distable[dnum].disease,np[i].disease);
				distable[dnum].people[distable[dnum].pnum++]=i;
				insertdis(np[i].disease,dnum);
				remain_dis++;
				dnum++;
			}
			else
				distable[result].people[distable[result].pnum++]=i;
		}
	}
	
	
	for(i=0;i<bnum;i++)
		if (buc[i].flag==true)
		{
			max=0;
			for(j=0;j<buc[i].dnum;j++)
				if(buc[i].dis[j].pnum>max)
					max=buc[i].dis[j].pnum;					//求出分離階段后桶中疾病人數最多的個數
			for(j=0;j<buc[i].dnum;j++)
			{
				if(buc[i].dis[j].pnum<max)
				{
					
					bnumber=searchdis(buc[i].dis[j].disease);
					if (bnumber<0)
						for(k=buc[i].dis[j].pnum;k<max;k++)
						{
							buc[i].dis[j].people[buc[i].dis[j].pnum++]=-1;
							cnum++;
							buc[i].dis[j].cnum++;
							buc[i].cnum++;
						}
					else
					{
						if(distable[bnumber].pnum>=(max-buc[i].dis[j].pnum))
						{
							for(k=buc[i].dis[j].pnum;k<max;k++)
							{	
								np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
								buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum-1];
								distable[bnumber].pnum--;
								remain--;
							}
							if(distable[bnumber].pnum==0)
								remain_dis--;
						}
						else
						{
							tmp=distable[bnumber].pnum;
							for(k=buc[i].dis[j].pnum;k<tmp;k++)
							{	
								np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
								buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum-1];
								distable[bnumber].pnum--;
								remain--;
							}
							remain_dis--;
							for(k=buc[i].dis[j].pnum;k<max;k++)
							{
								buc[i].dis[j].people[buc[i].dis[j].pnum++]=-1;
								cnum++;
								buc[i].dis[j].cnum++;
								buc[i].cnum++;
							}
						}
					}
				}
			}
			
		}
}

void assignment(void)
{
	int i,j,k,i1,i2,i3,i4,i5;
	struct order_node
	{
		int dnumber;
		int pnum;
	}order[20];
	int choose[10];
	int onum,min,bnumber;
	int tmp1,tmp2,tmp3;
	bool flag=false,flag2=false,flag3=false;
	
	/*for(i=0;i<bnum;i++)							//向已有桶內分配元素(優化)
	{
		int min=100000;
		for(j=0;j<buc[i].dnum;j++)
		{
			flag=false;
			bnumber=searchdis(buc[i].dis[j].disease);
			if(bnumber<0)
				flag=true;
			if(distable[bnumber].pnum==0)
				flag=true;
			if(flag==true)
				break;
			if(min>distable[bnumber].pnum)
				min=distable[bnumber].pnum;
		}
		if(flag==false)
			for(j=0;j<buc[i].dnum;j++)
			{
				bnumber=searchdis(buc[i].dis[j].disease);
				for(k=0;k<min;k++)
				{
					np[distable[bnumber].people[distable[bnumber].pnum]].flag=true;
					buc[i].dis[j].people[buc[i].dis[j].pnum++]=distable[bnumber].people[distable[bnumber].pnum--];
					remain--;
				}
				if(distable[bnumber].pnum==0)
					remain_dis--;
			}
		
	}*/
	
	flag=true;
	while(remain!=0)
	{
		if(flag==false||remain_dis<l)						//如果剩下的元素實在不能配分，退出
			break;
		
		else
		{
			flag=false;
			onum=0;
			for(i=0;i<dnum;i++)				//按剩余元素個數進行排列
			{
				if(distable[i].pnum!=0)
				{
					order[onum].dnumber=i;
					order[onum++].pnum=distable[i].pnum;
				}
			}
			for(i=1;i<onum;i++)
				for(j=onum-1;j>=i;j--)
					if(order[j-1].pnum<=order[j].pnum)
					{
						order[onum]=order[j-1];
						order[j-1]=order[j];
						order[j]=order[onum];
					}
		////////////////////////////////////	
			if(remain_dis<2*l)
				flag2=true;

			if(l==2)
			{
				for(i=0;i<onum;i++)
				{
					tmp1=1;							//找出l種滿足條件的疾病
					choose[0]=order[i].dnumber;
					for(j=i+1;j<onum;j++)
					{
						if(caculate(distable[order[i].dnumber].disease,distable[order[j].dnumber].disease)>limit)
						{
							choose[tmp1++]=order[j].dnumber;
							flag=true;
							break;
						}
					}
					if(flag==true)
						break;
				}
				if((flag2==true)&&(flag==true))
				{
					for(k=0;k<remain_dis;k++)
						choose[k]=order[k].dnumber;
					tmp1=k;
				}
			}
			else if (l==3)
			{
				for(i1=0;i1<onum-2;i1++)
				{
					choose[0]=order[i1].dnumber;
					for(i2=i1+1;i2<onum-1;i2++)
					{
						tmp1=1;
						if(caculate(distable[order[i1].dnumber].disease,distable[order[i2].dnumber].disease)>limit)
						{	
							choose[tmp1++]=order[i2].dnumber;
							for(i3=i2+1;i3<onum;i3++)
							{
								tmp1=2;
								if((caculate(distable[order[i1].dnumber].disease,distable[order[i3].dnumber].disease)>limit)&&(caculate(distable[order[i2].dnumber].disease,distable[order[i3].dnumber].disease)>limit))
								{
									choose[tmp1++]=order[i3].dnumber;
									flag=true;
									break;
								}
							}
						}
						if(flag==true)
							break;
					}
					if(flag==true)
						break;
				}
				if((flag2==true)&&(flag==true))
				{
					for(k=0;k<remain_dis;k++)
						choose[k]=order[k].dnumber;
					tmp1=k;
				}
			}
			else if (l==5)
			{
				for(i1=0;i1<onum-4;i1++)
				{
					choose[0]=order[i1].dnumber;
					for(i2=i1+1;i2<onum-3;i2++)
					{
						tmp1=1;
						if(caculate(distable[order[i1].dnumber].disease,distable[order[i2].dnumber].disease)>limit)
						{	
							choose[tmp1++]=order[i2].dnumber;
							for(i3=i2+1;i3<onum-2;i3++)
							{
								tmp1=2;
								flag3=true;
								for(i=0;i<tmp1;i++)
									if(caculate(distable[choose[i]].disease,distable[order[i3].dnumber].disease)<=limit)
										flag3=false;
								if(flag3==true)
								{
									choose[tmp1++]=order[i3].dnumber;
									for(i4=i3+1;i4<onum-1;i4++)
									{
										tmp1=3;
										flag3=true;
										for(i=0;i<tmp1;i++)
											if(caculate(distable[choose[i]].disease,distable[order[i4].dnumber].disease)<=limit)
												flag3=false;
										if(flag3==true)
										{
											choose[tmp1++]=order[i4].dnumber;
											for(i5=i4+1;i5<onum;i5++)
											{
												tmp1=4;
												flag3=true;
												for(i=0;i<tmp1;i++)
													if(caculate(distable[choose[i]].disease,distable[order[i5].dnumber].disease)<=limit)
														flag3=false;
												if(flag3==true)
												{
													choose[tmp1++]=order[i5].dnumber;
													flag=true;
													break;
												}
											}
										}
										if(flag==true)
											break;
									}
								}
								if(flag==true)
									break;
							}
						}
						if(flag==true)
							break;
					}
					if(flag==true)
						break;
				}
				if((flag2==true)&&(flag==true))
				{
					int count=0;
					for(k=0;k<remain_dis;k++)
						choose[k]=order[k].dnumber;
					tmp1=k;
				}
			}
			
			
//////////////////////////////////
			int ll=tmp1;
			if(flag==true)						//找到了滿足要求的l種疾病
			{
				for(i=0;i<ll;i++)
					strcpy(SA[i].disease,distable[choose[i]].disease);
				tmp2=f(tmp1);
				tmp3=searchhash(tmp2, SA[tmp1].disease);
				if(tmp3<0)						//沒有當前桶，需要建立新桶
				{
					buc[bnum].flag=true;
					buc[bnum].dnum=0;
					buc[bnum].cnum=0;
					for(i=0;i<ll;i++)
					{
						strcpy(buc[bnum].dis[buc[bnum].dnum].disease,distable[choose[i]].disease);
						buc[bnum].dis[buc[bnum].dnum].cnum=0;
						buc[bnum].dis[buc[bnum].dnum].pnum=0;
						buc[bnum].dnum++;
					}
					inserthash(tmp2,SA[tmp1].disease, bnum);
					tmp3=bnum;
					bnum++;
				}
				tmp1=(distable[choose[ll-1]].pnum+1)/2;
				for(i=0;i<ll;i++)						//向桶里添加元素
				{