$HEAP_DISPOSE ON$ Program HoleInOne(input,output); const maxhole=10000; type parents=(none,min1,plus1,maal2,over2); field=record distance:integer; next:parents; end; queue=record index:integer; dist:integer; end; qarray=array[1..maxhole] of queue; qpointer=^qarray; var r,runs:integer; hole:array[1..maxhole] of field; size:integer; fromhole,tohole:integer; Procedure Init; var i:integer; begin for i:=1 to size do with hole[i] do begin distance:=maxint; next:=none; end; end; { Init } Procedure SearchRoute; var q:qpointer; (* Index to hole *) qstart,qend:integer; begin New(q); qstart:=1; q^[1].index:=tohole; q^[1].dist:=0; qend:=1; while (qend>=qstart) do begin if (q^[qstart].index*2<=size) then with hole[q^[qstart].index*2] do begin if (q^[qstart].dist<distance) then begin distance:=q^[qstart].dist; next:=over2; qend:=qend+1; q^[qend].index:=q^[qstart].index*2; q^[qend].dist:=q^[qstart].dist+1; end; end; if (q^[qstart].index<size) then with hole[q^[qstart].index+1] do begin if (q^[qstart].dist<distance) then begin distance:=q^[qstart].dist; next:=min1; qend:=qend+1; q^[qend].index:=q^[qstart].index+1; q^[qend].dist:=q^[qstart].dist+1; end; end; if (q^[qstart].index>1) then with hole[q^[qstart].index-1] do begin if (q^[qstart].dist<distance) then begin distance:=q^[qstart].dist; next:=plus1; qend:=qend+1; q^[qend].index:=q^[qstart].index-1; q^[qend].dist:=q^[qstart].dist+1; end; end; if (q^[qstart].index mod 2=0) then with hole[q^[qstart].index div 2] do begin if (q^[qstart].dist<distance) then begin distance:=q^[qstart].dist; next:=maal2; qend:=qend+1; q^[qend].index:=q^[qstart].index div 2; q^[qend].dist:=q^[qstart].dist+1; end; end; qstart:=qstart+1; end; Dispose(q); end; { SearchRoute } Procedure PrintPath; var current:integer; begin current:=fromhole; Write(current:1); while (current<>tohole) do begin case hole[current].next of min1: current:=current-1; plus1: current:=current+1; maal2: current:=current*2; over2: current:=current div 2; end; { case } Write(' ',current:1); end; WriteLn; end; begin ReadLn(runs); for r:=1 to runs do begin ReadLn(size); Init; ReadLn(fromhole,tohole); hole[tohole].distance:=0; SearchRoute; PrintPath; end; end.