1248 Safecracker

問題概要

鍵は、入力文字列から異なる5文字を任意の順番で選び、
A=1,B=2...Z=26で整数を対応させて、v,w,x,y,zとしたときに

v - w2 + x3 - y4 + z5 = target

の式を満たすようなもののうち、最も辞書順で最後に来るものである。
入力文字列およびtargetが与えられるとき、鍵を求めよ。

解法

全探索。枝刈り全くなしで通る。

ソースコード

int t,n; char in[30];
char ans[6],tmp[6];

void solve(int c,int sum)
{
	if(c<0)
	{
		if(sum==t&&strcmp(tmp,ans)>0)strcpy(ans,tmp);
		return;
	}
	for(int i=n-1;i>=0;i--)if(in[i])
	{
		tmp[c]=in[i]; in[i]=0;
		
		//int s=0; rep(j,c+1)s+=(int)pow(26,j+1.0);
		//if(abs(s)>=abs(t-sum))
		solve(c-1,sum-(int)pow(-tmp[c]+'A'-1,c+1.0));
		
		in[i]=tmp[c];
	}
}
int main()
{
	while(scanf("%d%s",&t,in),t!=0||strcmp(in,"END"))
	{
		ans[0]=0; n=strlen(in); sort(in,in+n);
		solve(4,0);
		puts(ans[0]?ans:"no solution");
	}
	return 0;
}