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);
     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

Please read the guidelines before commenting.


There are no comments at the moment.