记录编号	33584	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 吉祥数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-11-11 14:03:52	内存使用	1.96 MiB

#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

const int weisqr[10][9]={
{0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1},
{1,2,4,8,16,32,64,128,256},
{1,3,9,27,81,243,729,2187,6561},
{1,4,16,64,256,1024,4096,16384,65536},
{1,5,25,125,625,3125,15625,78125,390625},
{1,6,36,216,1296,7776,46656,279936,1679616},
{1,7,49,343,2401,16807,117649,823543,5764801},
{1,8,64,512,4096,32768,262144,2097152,16777216},
{1,9,81,729,6561,59049,531441,4782969,43046721}};
/*
int sqrwei(int num,int level)
{
	int total=0,wei,sqred,lt;
	while (num)
	{
		lt=level;
		sqred=1;
		wei=num%10;
		while (lt)
		{
			sqred*=wei;
			lt--;
		}
		total+=sqred;
		num/=10;
	}
	return(total);
}
*/
int cal(int num,int level)
{
	int total=0,temp;
	while (num)
	{
		temp=num%10;
		total+=weisqr[temp][level];
		num/=10;
	}
	return(total);
}

void swapint(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void swapbool(bool& a,bool& b)
{
	if (a==b)
		return;
	else
	{
		a=!a;
		b=!b;
	}
}

void qqsort(int* a,int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=a[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (a[ll]<temp)
			ll++;
		while (temp<a[rr])
			rr--;
		if (ll<=rr)
		{
			swapint(a[ll],a[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(a,l,rr);
	if (ll<r)
		qqsort(a,ll,r);
}

int main(void)
{
	freopen("ghillie.in","r",stdin);
	freopen("ghillie.out","w",stdout);
	int i,j,n=1,turnnow,turn,a[201]={0},num;
	bool newout[201]={false},out[201]={false};
	scanf("%d\n",&turn);
	while (scanf("%d",&a[n])==1)
		n++;
	n--;
	for (turnnow=1;turnnow<=turn;turnnow++)
	{
		memset(newout,0,sizeof(newout));
		for (i=1;i<=n;i++)
		{
//			if (!out[i])
//				num=sqrwei(a[i],turnnow+1);
//			if (num>=1&&num<=n)
//				newout[num]=true;
			if (!out[i])
				num=cal(a[i],turnnow+1);
			for (j=1;j<=n;j++)
				if (num==a[j])
					newout[j]=true;
		}
		for (i=1;i<=n;i++)
			if (newout[i])
				out[i]=true;
	}
	for (i=1,j=n;i<=j;)
	{
		while (!out[i])
			i++;
		while (out[j])
			j--;
		if (i<=j)
		{
			swapbool(out[i],out[j]);
			swapint(a[i],a[j]);
			i++;
			j--;
		}
	}
	qqsort(a,1,j);
	for (i=1;i<=j;i++)
		printf("%d ",a[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return(0);
}