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.
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); read(kk,x,y,z,x0,y0,z0); 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); readln; 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; }
Code mẫu của ladpro98
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); readln(inp,k); readln(inp,s.a,s.b,s.c,la,lb,lc); i:=0; while not eof(inp) do begin inc(i); readln(inp,c[i].a,c[i].b,c[i].c,c[i].pa,c[i].pb,c[i].pc); 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); read(f,n); read(f,z,s,m); read(f,z0,s0,m0); sl:=0; while not eof(f) do begin inc(sl); read(f,z1[sl],s1[sl],m1[sl]); read(f,z2[sl],s2[sl],m2[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; }
Comments