TRIBE - Bộ lạc
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
program TRIBE;
const
FINP='';
FOUT='';
MAXN=52;
type
st=string[MAXN];
var
a,b,c,n:longint;
cost,sa,sb:array[1..MAXN] of longint;
word:array[1..MAXN] of st;
pre,d:array[0..MAXN,0..MAXN,0..MAXN] of longint;
procedure inp;
var
ch:char;
f:text;
i,j:longint;
begin
assign(f,FINP); reset(f);
readln(f,n);
readln(f,a,b,c);
for i:=1 to n do
begin
repeat
read(f,ch);
if ch<>' 'then word[i]:=word[i]+ch;
if ch='a' then inc(sa[i])
else if ch='b' then inc(sb[i]);
until ch=' ';
readln(f,cost[i]);
end;
close(f);
end;
procedure init;
var
i:longint;
begin
for i:=1 to MAXN do
begin
word[i]:='';
sa[i]:=0; sb[i]:=0;
cost[i]:=0;
end;
end;
procedure solve;
var
i,aa,bb,u:longint;
begin
for i:=1 to c+1 do
begin
for u:=1 to n do
for aa:=0 to a do
for bb:=0 to b do
if (aa>=sa[u]) and (bb>=sb[u]) then
if d[i,aa,bb]<d[i-1,aa-sa[u],bb-sb[u]]+cost[u] then
begin
d[i,aa,bb]:=d[i-1,aa-sa[u],bb-sb[u]]+cost[u];
pre[i,aa,bb]:=u;
end;
end;
end;
procedure ans;
var
f:text;
i,aa,bb,li,la,lb:longint;
procedure trace(i,a,b:longint);
var
u:longint;
begin
u:=pre[i,a,b];
if u=0 then exit;
write(f,word[u]);
if i<li+1 then write(f,' ');
if i>1 then trace(i-1,a-sa[u],b-sb[u]);
end;
begin
assign(f,FOUT); rewrite(f);
li:=0; la:=0; lb:=0;
for i:=c+1 downto 1 do
for aa:=0 to a do
for bb:=0 to b do
if d[i,aa,bb]>d[li,la,lb] then
begin
li:=i;
la:=aa;
lb:=bb;
end;
if li>0 then trace(li,la,lb);
close(f);
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure swaps(var a,b:st);
var
temp:st;
begin
temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
i,j:longint;
mid:st;
begin
mid:=word[(l+r) div 2];
i:=l; j:=r;
repeat
while word[i]<mid do inc(i);
while word[j]>mid do dec(j);
if i<=j then
begin
swaps(word[i],word[j]);
swap(sa[i],sa[j]);
swap(sb[i],sb[j]);
swap(cost[i],cost[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
begin
init;
inp;
sort(1,n);
solve;
ans;
end.