1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
const int maxn=100050;
int T,n,m,maxx;
int tire[maxn][30],cnt[maxn],num;
string s,temp;
char ans[maxn],t[maxn];
void insert(string s,int x)
{
int p=0;
for(int i=0;i<s.size();i++)
{
if(tire[p][s[i]-'a']) p=tire[p][s[i]-'a'];
else
{
tire[p][s[i]-'a']=++num;
p=num;
}
cnt[p]+=x;
}
}
void dfs(int d,int ed,int sum,int p)
{
if(d==ed)
{
if(sum>maxx)
{
maxx=sum;
memset(ans,0,sizeof(ans));
for(int i=0;i<ed;i++) ans[i]=t[i];
}
return ;
}
int tt=temp[d]-'0'-1,q;
if(tt==6) tt=(tt-1)*3,q=4;
else if(tt==7) tt=19,q=3;
else if(tt==8) tt=22,q=4;
else tt=(tt-1)*3,q=3;
for(int i=tt;i<tt+q;i++)
{
if(tire[p][i])
{
t[d]='a'+i;
dfs(d+1,ed,cnt[tire[p][i]],tire[p][i]);
t[d]=0;
}
else continue;
}
return ;
}
int main()
{
cin>>T;
for(int tim=1;tim<=T;tim++)
{
cout<<"Scenario #"<<tim<<":"<<endl;
memset(tire,0,sizeof(tire));
memset(cnt,0,sizeof(cnt));num=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>s>>x;
insert(s,x);
}
cin>>m;
while(m--)
{
cin>>s;
for(int i=0;s[i]!='1';i++)
{
memset(t,0,sizeof(t));maxx=0;
memset(ans,0,sizeof(ans));
temp=s.substr(0,i+1);
dfs(0,i+1,0,0);
if(!maxx) cout<<"MANUALLY"<<endl;
else
{
for(int j=0;j<i+1;j++) cout<<ans[j];
cout<<endl;
}
}
if(m!=0) cout<<endl;
}
cout<<endl<<endl;
}
return 0;
}
|