## Editorial for VM 08 Bài 10 - Bộ lạc

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=51;
var a:array[0..maxn] of string;
b,d,e,re:array[1..maxn] of longint;
f:array[0..maxn,0..maxn,-1..maxn] of longint;
n,x,y,z:longint;
kq:ansistring;

procedure rf;
var i,t:longint;  c:char; code:integer; s:string;
begin
for i:=1 to n do
begin
t:=pos(' ',a[i]);
s:=copy(a[i],t+1,length(a[i])-t);
delete(a[i],t,length(a[i])-t+1);
val(s,b[i],code);
end;
end;

procedure sort;
var i,j,t:longint; p:string;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]<a[j] then
begin
p:=a[i]; a[i]:=a[j]; a[j]:=p;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
end;
end;

procedure calc;
var i,j:longint;
begin
for i:=1 to n do
for j:=1 to length(a[i]) do
if a[i,j]='a' then inc(d[i])
else inc(e[i]);
end;

procedure pr;
var i,j,k,p:longint;
begin
sort;
calc;
f[0,0,-1]:=1;
for i:=1 to n do
for j:=d[i] to x do
for k:=e[i] to y do
for p:=0 to z do
if (f[j-d[i],k-e[i],p-1]>0) and (f[j,k,p]<f[j-d[i],k-e[i],p-1]+b[i]) then
f[j,k,p]:=f[j-d[i],k-e[i],p-1]+b[i];
end;

procedure att(j,k,p:longint);
var i,last:longint; s:ansistring;
begin
fillchar(re,sizeof(re),0);
last:=n;
while p>=0 do
begin
for i:=last downto 1 do
if (d[i]<=j) and (e[i]<=k) and (f[j,k,p]=f[j-d[i],k-e[i],p-1]+b[i]) then
begin
inc(re[i]);
j:=j-d[i]; k:=k-e[i]; p:=p-1;
last:=i;
break;
end;
end;
for i:=n downto 1 do
for j:=1 to re[i] do
s:=s+a[i]+' ';
if s<kq then kq:=s;
end;

procedure trace;
var i,jj,kk,pp,j,k,p,last,res:longint;
begin
kq:='z';
res:=0;
for j:=0 to x do
for k:=0 to y do
for p:=-1 to z do
if f[j,k,p]>res then
res:=f[j,k,p];
for j:=0 to x do
for k:=0 to y do
for p:=-1 to z do
if f[j,k,p]=res then att(j,k,p);
writeln(kq);
end;

begin
rf;
pr;
trace;
end.


{$H+} program TRIBE; uses math,sysutils; const maxn=50; fi=''; type e=record a,b,w:longint; s:string; end; var f,choose:array[0..maxn,0..maxn,0..maxn] of longint; n,mx,my,mz,d:longint; p:array[1..maxn] of e; procedure input; var inp:text; i,j:longint; s:string; te:e; begin assign(inp,fi);reset(inp); readln(inp,n); readln(inp,mx,my,mz); for i:=1 to n do begin readln(inp,s); for j:=1 to length(s) do begin if s[j] = ' ' then break; if s[j] = 'a' then inc(p[i].a) else inc(p[i].b); end; p[i].w:=StrToInt(copy(s,j+1,length(s)-j)); p[i].s:=copy(s,1,j-1); end; close(inp); for i:=1 to n do for j:=i+1 to n do if p[i].s>p[j].s then begin te:=p[i]; p[i]:=p[j]; p[j]:=te; end; end; procedure dp; var i,x,y,z:longint; begin for x:=0 to mx do for y:=0 to my do for z:=1 to mz+1 do begin for i:=1 to n do if (x>=p[i].a) and (y>=p[i].b) and (f[x,y,z]<f[x-p[i].a,y-p[i].b,z-1]+p[i].w) then begin f[x,y,z]:=f[x-p[i].a,y-p[i].b,z-1]+p[i].w; choose[x,y,z]:=i; end; end; end; procedure output; var i,x,y,z:longint; begin x:=mx;y:=my;z:=mz+1; while choose[x,y,z]>0 do begin d:=choose[x,y,z]; dec(x,p[d].a); dec(y,p[d].b); dec(z); write(p[d].s); if choose[x,y,z]>0 then write(' '); end; end; begin input; dp; output; end.  #### Code mẫu của RR {$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);
for i:=1 to n do
begin
repeat
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=' ';
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.


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,x,y,z,gt[51],soa[51],sob[51],f[51][51][55],temp;
string s[51],the1,the2,the;

int main(){
//freopen("TRIBE.in","r",stdin);
scanf("%d %d %d %d",&n,&x,&y,&z);
for(int i = 1;i<=n;i++)
cin>>s[i]>>gt[i];
memset(f,0,sizeof(f));
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++){
the1 = s[i]+' '+s[j];
the2 = s[j]+' '+s[i];
if(the1.compare(the2)<0){
the = s[i];
s[i] = s[j];
s[j] = the;
temp = gt[i];
gt[i] = gt[j];
gt[j] = temp;
}
}
for(int i = 1;i<=n;i++){
soa[i] = 0; sob[i] = 0;
for(int j = 0;j<s[i].length();j++)
if(s[i][j]=='a') soa[i]++;
else sob[i]++;
}

for(int i = 1;i<=z+1;i++){
for(int tx = 0;tx<=x;tx++)
for(int ty=0;ty<=y;ty++){
f[tx][ty][i] = f[tx][ty][i-1];
for(int j = 1;j<=n;j++)
if(tx-soa[j]>=0 && ty-sob[j]>=0)
f[tx][ty][i] >?= f[tx-soa[j]][ty-sob[j]][i-1]+ gt[j];
}
}
z++;
int run = f[x][y][z];
//printf("%d\n",run);
//while(f[x][y][z] == f[x][y][z-1]) z--;
int l;
while(z>0){
l = z;
// printf("%d %d %d %d\n",run,x,y,z);
for(int i = 1;i<=n;i++){
if(x>=soa[i] && y>=sob[i])
if(run == f[x-soa[i]][y-sob[i]][z-1]+gt[i]){
cout<<s[i]<<" ";
run -= gt[i];
x -= soa[i];
y -= sob[i];
z--;
break;
}
}
if(l==z) z--;
// printf("%d %d %d %d\n",run,x,y,z);
//getch();
}
// getch();
}


#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int f[52][52][52];
vector< pair<string,int> > v;
string s[52];
int a[52],b[52],val[52];
int n,maxx,maxy,maxz;

int rec(int x,int y,int z)
{
if (f[x][y][z] != -1) return f[x][y][z];
int best = 0;
if (!z)
{
for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,val[i]);
}
else
for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,rec(x - a[i],y - b[i],z - 1) + val[i]);
f[x][y][z] = best;  return best;
};

void track(int x,int y,int z,bool first)
{
if (!f[x][y][z]) return;
if (!first) printf(" ");
if (!z)
{
for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i])
{
cout << s[i]; break;
};
}
else
for (int i = 0; i < n; i++)
if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i] + rec(x - a[i],y - b[i],z - 1))
{
cout << s[i];  track(x - a[i],y - b[i],z - 1,false);  break;
};
};

int main()
{
//    freopen("tribe.in","r",stdin);
//    freopen("tribe.ou","w",stdout);
scanf("%d", &n);
scanf("%d %d %d", &maxx, &maxy, &maxz);
for (int i = 0; i < n; i++)
{
string st;  int k;
cin >> st >> k;
v.push_back(make_pair(st,k));
};
sort(v.begin(),v.end());
for (int i = 0; i < n; i++)
{
a[i] = 0;  b[i] = 0; s[i] = v[i].first; val[i] = v[i].second;
for (int j = 0; j < s[i].size(); j++) if (s[i][j] == 'a') a[i]++; else b[i]++;
};
memset(f,-1,sizeof(f));
int tmp = rec(maxx,maxy,maxz);
track(maxx,maxy,maxz,true);
};


#### Code mẫu của khuc_tuan

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

static class Word {
String w;
int na, nb;
int value;
}

static int n;
static int x, y, z;
static Word[] a;
static int[][][][] F;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
z = sc.nextInt();
sc.nextLine();
a = new Word[n];
for (int i = 0; i < n; ++i) {
String[] tmp = sc.nextLine().split(" ");
a[i] = new Word();
a[i].w = tmp[0];
a[i].value = Integer.parseInt(tmp[1]);
}
Arrays.sort(a, new Comparator<Word>() {
public int compare(Word w1, Word w2) {
return w1.w.compareTo(w2.w);
}
});
for (int i = 0; i < n; ++i)
for (int j = 0; j < a[i].w.length(); ++j)
if (a[i].w.charAt(j) == 'a')
++a[i].na;
else
++a[i].nb;
F = new int[x + 1][y + 1][z + 1][2];
for (int[][][] a3 : F)
for (int[][] a2 : a3)
for (int[] a1 : a2)
Arrays.fill(a1, -1);
System.out.println(truyvet(x, y, z, 0));
}

static String truyvet(int x, int y, int z, int need) {
int res = calc(x, y, z, need);
// if (z > 0 && res == calc(x, y, z - 1, 0))
// return " " + truyvet(x, y, z - 1, 0);
for (int k = 0; k < a.length; ++k) {
if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
if (res == now + a[k].value)
return (need == 0 ? "" : " ") + a[k].w
+ truyvet(x - a[k].na, y - a[k].nb, z - need, 1);
}
}
return "";
}

static int calc(int x, int y, int z, int need) {
if (F[x][y][z][need] != -1)
return F[x][y][z][need];

int res = 0;
// if (z > 0)
// res = Math.max(res, calc(x, y, z - 1, 0));

for (int k = 0; k < a.length; ++k)
if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
res = Math.max(res, now + a[k].value);
}

return F[x][y][z][need] = res;
}
}