## Editorial for VOI 05 Bài 3 - Bộ sưu tập

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 fi='';
fo='';
maxn=16000;
var n,x,y,z,x0,y0,z0,kk,res,num:longint;
re:array[1..maxn,0..3] of longint;
a:array[1..maxn,1..6] of longint;
q:array[1..maxn,1..3] of longint;
d:array[0..4,0..4,0..4] of longint;
dau:array[0..4,0..4,0..4,0..4,0..4,0..4] of byte;

procedure rf;
var i,j,k:longint;
begin
assign(input,fi);
reset(input);
n:=0;
for i:=0 to 4 do
for j:=0 to 4 do
for k:=0 to 4 do
dau[i,j,k,i,j,k]:=1;
while not eof do
begin
inc(n);
for i:=1 to 6 do read(a[n,i]);
if dau[a[n,1],a[n,2],a[n,3],a[n,4],a[n,5],a[n,6]]=0 then
dau[a[n,1],a[n,2],a[n,3],a[n,4],a[n,5],a[n,6]]:=1
else dec(n);
end;
close(input);
end;

function check(r,s,t,x,y,z:longint):boolean;
begin
check:=(r>=0) and (s>=0) and (t>=0) and (x<5) and (y<5) and (z<5);
end;

procedure pr;
var i,j,r,s,t,rr,ss,tt:longint;
begin
fillchar(d,sizeof(d),0);
d[x,y,z]:=1; i:=1; num:=1; q[1,1]:=x; q[1,2]:=y; q[1,3]:=z;
repeat
if (q[i,1]>=x0) and (q[i,2]>=y0) and (q[i,3]>=z0) then
begin
inc(i); continue;
end;
for j:=1 to n do
begin
r:=q[i,1]-a[j,1]; s:=q[i,2]-a[j,2]; t:=q[i,3]-a[j,3];
rr:=r+a[j,4]; ss:=s+a[j,5]; tt:=t+a[j,6];
if check(r,s,t,rr,ss,tt) then
begin
if (d[rr,ss,tt]=0) then
begin
inc(num);
q[num,1]:=rr; q[num,2]:=ss; q[num,3]:=tt;
d[rr,ss,tt]:=d[q[i,1],q[i,2],q[i,3]]+1;
end
else
begin
if d[rr,ss,tt]>d[q[i,1],q[i,2],q[i,3]]+1 then
d[rr,ss,tt]:=d[q[i,1],q[i,2],q[i,3]]+1;
end;
end;
end;
inc(i);
until i>num;
end;

procedure wf;
var i,j,k:longint;
begin
assign(output,fo);
rewrite(output);
res:=0;
for i:=x0 to 4 do
for j:=y0 to 4 do
for k:=z0 to 4 do
if (d[i,j,k]>1) and (d[i,j,k]-1<=kk) then
begin
inc(res);
re[res,0]:=i; re[res,1]:=j; re[res,2]:=k;
re[res,3]:=d[i,j,k]-1;
end;
if res=0 then write(-1)
else
begin
writeln(res);
for i:=1 to res do
begin
for j:=0 to 2 do write(re[i,j],' ');
writeln(re[i,3]);
end;
end;
close(output);
end;

begin
rf;
pr;
wf;
end.


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

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)

struct state {
int z, s, m, k;
state() {}
state(int z, int s, int m, int k): z(z), s(s), m(m), k(k) {}
state(int z, int s, int m): z(z), s(s), m(m), k(0) {}
bool operator < (const state &a) const {
return z != a.z ? z < a.z : s != a.s ? s < a.s : m != a.m ? m < a.m : k != a.k ? k < a.k : 0;
}
};

bool vst[5][5][5];
vector<pair<state, state> > conv;
int z, s, m, z0, s0, m0, k;

void enter() {
scanf("%d%d%d%d%d%d%d", &k, &z, &s, &m, &z0, &s0, &m0);
for(int z1,s1,m1,z2,s2,m2; scanf("%d%d%d%d%d%d",&z1,&s1,&m1,&z2,&s2,&m2) == 6; )
conv.push_back(make_pair(state(z1,s1,m1), state(z2,s2,m2)));
}

void solve() {
queue<state> q; q.push(state(z, s, m)); vst[z][s][m] = 1;
vector<state> res;
while(!q.empty()) {
state u = q.front(); q.pop();
//printf("* %d %d %d %d\n", u.z, u.s, u.m, u.k);
if(u.z >= z0 && u.s >= s0 && u.m >= m0) res.push_back(u);
else TR(conv, it) {
if(u.z >= it->first.z && u.s >= it->first.s && u.m >= it->first.m && u.k + 1 <= k) {
int z = u.z - it->first.z + it->second.z;
int s = u.s - it->first.s + it->second.s;
int m = u.m - it->first.m + it->second.m;
if(z <= 4 && s <= 4 && m <= 4 && vst[z][s][m] == 0)
vst[z][s][m] = 1, q.push(state(z, s, m, u.k+1));
}
}
}
if(res.empty()) printf("-1\n");
else {
printf("%u\n", res.size());
sort(res.begin(), res.end());
TR(res, u) printf("%d %d %d %d\n", u->z, u->s, u->m, u->k);
}
}

int main() {
enter();
solve();
return 0;
}


program collect;
uses    math;
type    e=record
a,b,c:longint;
end;
e2=record
a,b,c,pa,pb,pc:longint;
end;
const   fi='';
maxn=100000;
var     s:e;
q:array[1..maxn] of e;
c:array[1..maxn] of e2;
p:array[1..maxn] of e;
avail:array[0..10,0..10,0..10] of boolean;
res:array[0..10,0..10,0..10] of longint;
k,la,lb,lc,d:longint;

procedure input;
var     inp:text;
i,j,t:longint;
begin

assign(inp,fi);reset(inp);
i:=0;
while not eof(inp) do
begin
inc(i);
end;
d:=i;
for i:=0 to 4 do
for j:=0 to 4 do
for t:=0 to 4 do
avail[i,j,t]:=true;
close(inp);
end;

function isValue(x:e):boolean;
begin
exit((x.a>=la) and (x.b>=lb) and (x.c>=lc));
end;

procedure bfs;
var     i,l,r:longint;
u,v:e;
begin
l:=1;r:=1;
q[1]:=s;
res[s.a,s.b,s.c]:=0;
avail[s.a,s.b,s.c]:=false;
while l<=r do
begin
u:=q[l];inc(l);
if isValue(u) or (res[u.a,u.b,u.c]>=k) then continue;
for i:=1 to d do
begin
if (u.a>=c[i].a) and (u.b>=c[i].b) and (u.c>=c[i].c) then

begin
v.a:=u.a-c[i].a+c[i].pa;
v.b:=u.b-c[i].b+c[i].pb;
v.c:=u.c-c[i].c+c[i].pc;
if (v.a<=4) and (v.b<=4) and (v.c<=4)
and avail[v.a,v.b,v.c] then
begin
avail[v.a,v.b,v.c]:=false;
inc(r);
q[r]:=v;
res[v.a,v.b,v.c]:=res[u.a,u.b,u.c]+1;
end;
end;
end;

end;
end;

procedure output;
var     i,j,t,count:longint;
begin
count:=0;
for i:=la to 4 do
for j:=lb to 4 do
for t:=lc to 4 do
if (not avail[i,j,t]) and (res[i,j,t]<=k)
then
begin
inc(count);
p[count].a:=i;
p[count].b:=j;
p[count].c:=t;
end;
if count=0 then write(-1) else
begin
writeln(count);
for i:=1 to count do
writeln(p[i].a,' ',p[i].b,' ',p[i].c,' ',res[p[i].a, p[i].b,p[i].c]);
end;
end;

begin
input;
bfs;
output;
end.


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

{\$R+,Q+}
const
FINP='';
FOUT='';
MAXN=1000;
oo=200;
var
d:array[0..4,0..4,0..4] of longint;
first,last,z0,m0,s0,z,m,s,n,sl:longint;
qz,qm,qs:array[1..200] of longint;
z1,m1,s1,z2,m2,s2:array[1..1000000] of longint;
procedure inp;
var
f:text;
begin
assign(f,FINP); reset(f);
sl:=0;
while not eof(f) do
begin
inc(sl);
end;
close(f);
end;
procedure ans;
var
f:text;
i,j,k,count:longint;
begin
assign(f,FOUT); rewrite(f);
count:=0;
for i:=z0 to 4 do
for j:=s0 to 4 do
for k:=m0 to 4 do
if d[i,j,k]<oo then inc(count);
if count=0 then
begin
writeln(f,-1);
close(f);
halt;
end;
writeln(f,count);
for i:=z0 to 4 do
for j:=s0 to 4 do
for k:=m0 to 4 do
if d[i,j,k]<oo then
writeln(f,i,' ',j,' ',k,' ',d[i,j,k]);
close(f);
end;
procedure solve;
var
i,j,k,ii,jj,kk,u:longint;
begin
for i:=0 to 4 do
for j:=0 to 4 do
for k:=0 to 4 do
d[i,j,k]:=oo;
first:=1; last:=1;
qz[1]:=z; qs[1]:=s; qm[1]:=m;
d[z,s,m]:=0;
while first<=last do
begin
i:=qz[first]; j:=qs[first]; k:=qm[first]; inc(first);
if d[i,j,k]=n then exit;
for u:=1 to sl do
if (i>=z1[u]) and (j>=s1[u]) and (k>=m1[u]) then
begin
ii:=i-z1[u]+z2[u];
jj:=j-s1[u]+s2[u];
kk:=k-m1[u]+m2[u];
if (ii<=4) and (jj<=4) and (kk<=4) and (d[ii,jj,kk]=oo) then
begin
d[ii,jj,kk]:=d[i,j,k]+1;
if (ii<z0) or (jj<s0) or (kk<m0) then
begin
inc(last);
qz[last]:=ii;
qs[last]:=jj;
qm[last]:=kk;
end;
end;
end;
end;
end;
begin
inp;
solve;
ans;
end.


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

#include <iostream>
#include <queue>
#include <map>
using namespace std;

int z, s, m, z0, s0, m0;
queue<int> qx, qy, qz;
int change[1010][6];
map<pair<int,pair<int,int> >, int> ma;
int n, k;

vector< pair<int, pair<int,int> > > ds;

int main() {
scanf("%d", &k);
scanf("%d%d%d%d%d%d", &z, &s, &m, &z0, &s0, &m0);
while(scanf("%d%d%d%d%d%d", change[n], change[n]+1, change[n]+2, change[n]+3, change[n]+4, change[n]+5)!=EOF) ++n;
qx.push(z);
qy.push(s);
qz.push(m);
ma[make_pair(z,make_pair(s,m))] = 0;
while(!qx.empty()) {
z = qx.front(); qx.pop();
s = qy.front(); qy.pop();
m = qz.front(); qz.pop();
int step = ma[make_pair(z,make_pair(s,m))];
if(z>=z0 && s>=s0 && m>=m0) {
ds.push_back(make_pair(z, make_pair(s,m)));
continue;
}
if(step>=k) continue;
for(int i=0;i<n;++i) {
if(z>=change[i][0] && s>=change[i][1] && m>=change[i][2]) {
int nz = z - change[i][0] + change[i][3];
int ns = s - change[i][1] + change[i][4];
int nm = m - change[i][2] + change[i][5];
if(nz>4 || ns>4 || nm>4) continue;
pair<int, pair<int,int> > state = make_pair(nz, make_pair(ns, nm));
if(!ma.count(state)) {
ma[state] = step + 1;
qx.push(nz);
qy.push(ns);
qz.push(nm);
}
}
}
}
if(ds.size()==0) cout << -1 << endl;
else {
cout << ds.size() << endl;
sort( ds.begin(), ds.end());
for(int i=0;i<ds.size();++i) {
cout << ds[i].first << " " << ds[i].second.first << " " << ds[i].second.second << " " << ma[ds[i]] << endl;
}
}
//system("pause");
return 0;
}