http://acm.hdu.edu.cn/showproblem.php?pid=1298
//1254514 2009-04-10 15:46:40 Accepted 1298 0MS 600K 2448 B C++ no way
#include<iostream>
#include
<string>
using namespace std;
int i,maxs;
char tel[103];
char seStr[28];
char putss[28];
char key[10][5= {{""}{""}{"abc1"}{"def1"}

{"ghi1"}{"jkl1"}{"mno1"}

{"pqrs"}{"tuv1"}{"wxyz"}}

typedef
struct dictree
{

struct dictree *child[26];

int num;
dictree()

{

for(i=0;i<26;i++)
child[i]
= NULL;
num
= 0;
}

~dictree()

{

for(i=0;i<26;i++)

if(child[i] != NULL)
delete child[i];
}

}
*dicTree;
dictree
*root;
int find(char ch[])//查找单词出现的频率
{
dictree
*= root;

int k=0,mins = 1000000;

while(1)

{

if(ch[k]=='\0' || p->child[ch[k]-'a']==NULL)

break;
p
= p->child[ch[k]-'a'];

if(mins > p->num)

{
mins
= p->num;

if(mins <= maxs)

return -1;
}

k
++;
}

if(ch[k] != '\0')

return -1;

return mins;
}

void dfs(int p,int t,int k)//深搜,t-界限，p-串中位置
{

int j;

if(p>t)

{
seStr[k]
='\0';

int m = find(seStr);

if(m > maxs)

{
strcpy(putss,seStr);
maxs
= m;
}

return ;
}

for(j=0;j<4;j++)

{

if(key[tel[p]-'0'][j] != '1')

{
seStr[k]
= key[tel[p]-'0'][j];
seStr[k
+1]='\0';

if(find(seStr) <= maxs) //该剪枝非常重要
continue;
dfs(p
+1,t,k+1);
}

}

}

void insert(char *s,int r) //构建字典树
{

struct dictree *now = root;

while(*s)

{

if(now->child[*s-'a'== NULL)
now
->child[*s-'a'= new dictree;
now
= now->child[*s-'a'];
now
->num += r;
s
++;
}

}

/*
void Delete(dicTree  &pt)
{
if(pt)
{
for(i=0;i<26;i++)
Delete(pt->child[i]);
}
free(pt);
pt = NULL;
}
*/

int main()
{

int j,n,r,t,cas=1;

char tmp[103];
cin
>>t;

while(t--)

{
cin
>>n; //单词的个数
root = new dictree;

while(n--)

{
scanf(
"%s%d",tmp,&r);
insert(tmp,r);
}

cin
>>n; //电话串的个数
cout<<"Scenario #"<<cas++<<":"<<endl;

while(n--

{
scanf(
"%s",tel);

int len = strlen(tel);

for(j=0;j<len;j++)

{

if(tel[j] == '1')//结束符
break;

if(j>25)//大于26个就没必要做了，肯定是没这个串
{
printf(
"MANUALLY\n");

continue;
}

maxs
= -1;
dfs(
0,j,0);

if(maxs == -1)
printf(
"MANUALLY\n");

else
printf(
"%s\n",putss);
}

printf(
"\n");
}

printf(
"\n");

//Delete(root);
}

return 0;
}