Đề thi Gặp gỡ

Bài 82/2001 - Gặp gỡ
(Dành cho học sinh PTTH)
Bài này có thể giải dễ dàng nhờ nhận xét sau:
- Nếu k robot ở các vị trí mà tổng toạ độ của chúng (x+y) có tính chẵn lẻ khác nhau thì chúng không bao giờ gặp nhau (vì chúng luôn luôn di chuyển, không có robot đứng yên). Như vậy, sau khi loại trường hợp trên, gọi A[t, i j] là số bước di chuyển ít nhất để robot t di chuyển từ vị trí ban đầu đến ô (i, j). Khi đó, số bước di chuyển ít nhất mà k robot phải di chuyển để gặp nhau là:
Min (max(A(t, i j) với 1 <= t <= k, 1 <= i <= M, 1 <= j <= N. Loang ngược lại, ta có đường đi của những robot này. 
Cài đặt chương trình:
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
Program MEET;
Uses crt;
Type point = record
 x,y:integer;
 End;
Const P:array[1..4,1..2] of integer=((0,1),(0,-1),(-1,0),(1,0));
 Q:string='LRDU';
 inp = 'MEET.INP';
 out = 'MEET.OUT';
Var v: array[1..10] of point;
 A: array[1..10,0..51,0..51] of integer;
 B: array[0..51,0..51] of byte;
 t: array[0..1,1..750] of point;
 M,N,K,c,d,e,g,h,l,i,j,Min,Max:integer;
 s,st:string;
 f:text;
Procedure NoSolution;
Begin
 Write(' # ');Readln;Halt;
End;
Procedure Input;
Begin
 Assign(f,inp);Reset(f);
 Readln(f,m,n,k);
 If k>0 then
 Begin
 Readln(f,v[1].x,v[1].y);
 e:=(v[1].x+v[1].y) mod 2;
 End;
 For c:=2 to k do
 Begin
 Read(f,v[c].x,v[c].y);
 If (v[c].x+v[c].y) mod 2e then NoSolution;
 End;
 Fillchar(b,sizeof(b),1);
 For c:=1 to m do
 For d:=1 to n do read(f,B[c,d]);
 Close(f);
End;
Procedure Solve;
Var Stop:boolean;
 z:array[0..1] of integer;
Begin
 For c:=0 to m+1 do
 For d:=0 to n+1 do
 If b[c,d]=0 then
 For e:=1 to k do a[e,c,d]:=MaxInt else
 For e:=1 to k do a[e,c,d]:=-1;
 For c:=1 to k do
 Begin
 l:=1;g:=0;h:=1;z[0]:=1;z[1]:=0;
 t[0,1]:=v[c];a[c,v[c].x,v[c].y]:=0;
 Stop:=false;
 While not Stop do
 Begin
 Stop:=true;
 For d:=1 to z[g] do
 For e:=1 to 4 do
 Begin
 i:=P[e,1]+t[g,d].x;
 j:=P[e,2]+t[g,d].y;
 If a[c,i,j]>l then
 Begin
 a[c,i,j]:=l;inc(z[h]);
 t[h,z[h]].x:=i;
 t[h,z[h]].y:=j;
 Stop:=false;
 End;
 End;
 l:=l+1;g:=1-g;h:=1-h;z[h]:=0;
 End;
 End;
 Min:=MaxInt;
 For c:=1 to m do
 For d:=1 to n do
 If b[c,d]1 then
 Begin
 max:=a[1,c,d];
 For e:=2 to k do
 If Max<a[e,c,d] then Max:=a[e,c,d];
 If Min>Max then
 Begin
 Min:=Max;
 i:=c;j:=d;
 End;
 End;
 If Min=MaxInt then NoSolution;
 Assign(f,out);Rewrite(f);
 For e:=1 to k do
 Begin
 c:=i;d:=j;s:='';
 While A[e,c,d]>0 do
 Begin
 l:=1;
 While a[e,c+P[l,1],d+P[l,2]]+1a[e,c,d] do l:=l+1;
 s:=Q[l]+s;
 c:=c+P[l,1];d:=d+P[l,2];
 End;
 l:=l-1+2*(l mod 2);
 st:=s[1]+Q[l];
 For g:=1 to (min-a[e,i,j]) div 2 do s:=st+s;
 Writeln(f,s);
 End;
 Close(f);
End;
BEGIN
 Clrscr;
 Input;
 Solve;
 Write('Complete - Open file ',out,' to view the result');
 Readln
END.
(Lời giải của bạn Vũ Lê An - Lớp 12T2 - Lê Khiết - Quảng Ngãi)
Nhận xét: Bài làm của bạn Vũ Lê An phần kết quả còn thiếu trường hợp. Sau đây là một cách cài đặt khác song thuật toán cũng giống với Vũ Lê An.
Mở rộng bài toán: Cho một đồ thị gồm N đỉnh, có k con robot ở k đỉnh V1, V2,.., Vk. Sau mỗi đơn vị thời gian tất cả các con robot đều phải chuyển động sang các đỉnh kề với đỉnh nó đang đứng. Hãy tìm cách di chuyển các con robot để chúng gặp nhau tại một điểm.
a. Trong đồ thị vô hướng
b. Trong đồ thị có hướng (k = 2 - Đề thi chọn đội tuyển Quốc gia)
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 65384,0,655360}
program Bai82_gap_go;{Author : Đỗ Đức Đông}
uses crt;
const max =50;
 max_robot =10;
 fi ='meet.inp';
 fo ='meet.out';
 tx :array[1..4]of integer=(0,-1,1,0);
 ty :array[1..4]of integer=(-1,0,0,1);
 h :string='LUDR';
var a :array[1..max,1..max]of byte;
 robot :array[1..max_robot,1..2]of byte;
 l :array[1..max,1..max,1..max_robot]of integer;
 q :array[1..max*max,1..2]of byte;
 dau,cuoi,m,n,r :integer;
 best,mx,my :integer;
 ok :boolean;
procedure docf;
var f :text;
 k,i,j:integer;
 begin
 assign(f,fi);
 reset(f);
 readln(f,m,n,r);
 for k:=1 to r do readln(f,robot[k,1],robot[k,2]);
 for i:=1 to m do
 for j:=1 to n do read(f,a[i,j]);
 close(f);
 end;
procedure loang(k:integer);
var x,y,s,u,v :integer;
 begin
 fillchar(q,sizeof(q),0);
 dau:=1;cuoi:=1;
 q[1,1]:=robot[k,1];
 q[1,2]:=robot[k,2];
 l[robot[k,1],robot[k,2],k]:=1;
 while dau<=cuoi do
 begin
 x:=q[dau,1];y:=q[dau,2];
 for s:=1 to 4 do
 begin
 u:=x+tx[s];
 v:=y+ty[s];
 if (u>0)and(v>0)and(u<=m)and(v<=n)and(a[u,v]=0)and(l[u,v,k]=0) then
 begin
 inc(cuoi);q[cuoi,1]:=u;q[cuoi,2]:=v;
 l[u,v,k]:=l[x,y,k]+1;
 end;
 end;
 inc(dau);
 end;
 end;
procedure lam;
var k,i,j :integer;
 meet :boolean;
 begin
 fillchar(l,sizeof(l),0);
 ok:=true;
 for k:=2 to r do
 if (robot[1,1]+robot[1,2]+robot[k,1]+robot[k,2]) mod 2=1 then ok:=false;
 if ok then
 begin
 best:=maxint;
 for k:=1 to r do loang(k);
 for i:=1 to m do
 for j:=1 to n do
 begin
 meet:=true;
 for k:=1 to r do meet:=meet and (l[i,j,k]>0) and (l[i,j,k]<best);
 if meet then
 begin
 best:=0;
 for k:=1 to r do
 if l[i,j,k]>best then
 begin
 best:=l[i,j,k];
 mx:=i;my:=j;
 end;
 end;
 end;
 ok:=best<maxint;
 end;
 end;
procedure ghif;
var f :text;
 k,kk :byte;
 lap :string;
 procedure viet(x,y:byte);
 var u,v,s :byte;
 begin
 for s:=1 to 4 do
 begin
 u:=x+tx[s];
 v:=y+ty[s];
 if (u>0)and(v>0)and(u<=m)and(v<=n)and(l[u,v,k]=l[x,y,k]-1) then
 begin
 if l[u,v,k]>1 then viet(u,v);
 write(f,h[5-s]);
 break;
 end;
 end;
 end;
 begin
 assign(f,fo);
 rewrite(f);
 if ok=false then write(f,'#')
 else
 begin
 for k:=1 to 4 do
 if (mx+tx[k]>0)and(my+ty[k]>0)and(mx+tx[k]<=m)and(my+ty[k]<=n) then
 if (a[mx+tx[k],my+ty[k]]=0) then kk:=k;
 lap:=h[kk]+h[5-kk];
 for k:=1 to r do
 begin
 if l[mx,my,k]>1 then viet(mx,my);
 for kk:=1 to (best-l[mx,my,k]) div 2 do write(f,lap);
 writeln(f);
 end;
 end;
 close(f);
 end;
BEGIN
 docf;
 lam;
 ghif;
END.
Bài 83/2001 - Các đường tròn đồng tâm
(Dành cho học sinh Tiểu học)
Đáp số: Các số được điền như sau: