记录编号	69424	评测结果	AAAAAAAAAA
题目名称	[金陵中学2007] 吉祥数	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-09-15 14:01:36	内存使用	0.31 MiB

#include<fstream>
#include<algorithm>
#include<deque>
using namespace std;
ifstream fi("ghillie.in");
ofstream fo("ghillie.out");
long long n,m,m_left,f[201];
bool boo[201];
deque <long long> deq;
long long chengfa[10][10]=
{
	{1,0,0,0,0,0,0,0,0,0},
	{1,1,1,1,1,1,1,1,1,1},
	{1,2,4,8,16,32,64,128,256,512},
	{1,3,9,27,81,243,729,2187,6561,19683},
	{1,4,16,64,256,1024,4096,16384,65536,262144},
	{1,5,25,125,625,3125,15625,78125,390625,1953125},
	{1,6,36,216,1296,7776,46656,279936,1679616,10077696},
	{1,7,49,343,2401,16807,117649,823543,5764801,40353607},
	{1,8,64,512,4096,32768,262144,2097152,16777216,134217728},
	{1,9,81,729,6561,59049,531441,4782969,43046721,387420489}
};
long long do_do(long long x,long long y)
{
	long long t=x,ans=0;
	while(t>0)
	{
		ans+=chengfa[t%10][y];
		t/=10;
	}
	return ans;
}
int main()
{
	fi>>n;
	m=0;
	while(!fi.eof())
	{
		m++;
		boo[m]=true;
		fi>>f[m];
	}
	m;
	sort(f+1,f+m+1);
	f[0]=m;//是个极限，编号都不可能＞f[f[0]]
	long long i,j,tmp,a;
	for(i=1;i<=n;i++)
	if(f[0]>0)
	{
		for(j=1;j<=m;j++)
		if(boo[j])
		{
			tmp=do_do(f[j],i+1);
			if(tmp<=f[f[0]])deq.push_back(tmp);
		}
		sort(deq.begin(),deq.end());
		//for(j=0;j<deq.size();j++)
		//	fo<<deq[j]<<' ';
		//fo<<endl;
		a=1;
		while(a<=m&&deq.size()>0)
		{
			if((!boo[a])||(f[a]<deq.front())){a++;continue;}
			if(f[a]==deq.front())
			{
				boo[a]=false;
				a++;
				deq.pop_front();
				continue;
			}
			if(f[a]>deq.front())deq.pop_front();
		}
		deq.clear();
		while(!boo[f[0]]&&f[0]>0)f[0]--;
	}
	for(i=1;i<=m;i++)
		if(boo[i])fo<<f[i]<<' ';
	fo<<endl;
	return 0;
}