Hướng dẫn giải của VOI 05 Bài 3 - Bộ sưu tập
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận