Can anyone of those who have solved the problem tell me
how ? If you use recursion 31 is a extremely enormous limit
and it works years. So a formula? How?

it takes 2^k-1 steps to move k disk from one peg to another

QH@

> Can anyone of those who have solved the problem tell me
> how ? If you use recursion 31 is a extremely enormous
limit
> and it works years. So a formula? How?
I am facing the same problem. Time limite exceeding. Could
somone advise me how to optimize the algorithm ?.program
hanoit;
const maxN=31;
var i,n,nmove:integer;
    current,target:array[1..maxN] of integer;

function sama:boolean;
var i:integer;
begin
  sama:=true;
  for i:=1 to N do if current[i]<>target[i] then
  begin
    sama:=false;
    exit;
  end;
end;

procedure move(n,to_:integer);
begin
  inc(nmove);
  current[n]:=to_;
  if sama then begin writeln(nmove); readln; halt; end;
end;

procedure hanoi (n, from, to_, temp : integer);
begin
  if n > 0 then
  begin
    hanoi (n-1,from,temp,to_);
    move(n,to_);
    hanoi(n-1,temp,to_,from);
  end;
end;
begin
  nmove:=0;
  read(N);
  for i:=1 to N do
  begin
    read(target[i]);
    current[i]:=1;
  end;
  if sama then begin writeln(nmove); readln; halt; end
  else hanoi(N,1,2,3);
  writeln(-1 );
end.

First of all you shouldn't use readln after you print the
solution.It'll wait forever!

Good luck!

> I am facing the same problem. Time limite exceeding. Could
> somone advise me how to optimize the algorithm ?.program
> hanoit;
> const maxN=31;
> var i,n,nmove:integer;
>     current,target:array[1..maxN] of integer;
>
> function sama:boolean;
> var i:integer;
> begin
>   sama:=true;
>   for i:=1 to N do if current[i]<>target[i] then
>   begin
>     sama:=false;
>     exit;
>   end;
> end;
>
> procedure move(n,to_:integer);
> begin
>   inc(nmove);
>   current[n]:=to_;
>   if sama then begin writeln(nmove); readln; halt; end;
> end;
>
> procedure hanoi (n, from, to_, temp : integer);
> begin
>   if n > 0 then
>   begin
>     hanoi (n-1,from,temp,to_);
>     move(n,to_);
>     hanoi(n-1,temp,to_,from);
>   end;
> end;
> begin
>   nmove:=0;
>   read(N);
>   for i:=1 to N do
>   begin
>     read(target[i]);
>     current[i]:=1;
>   end;
>   if sama then begin writeln(nmove); readln; halt; end
>   else hanoi(N,1,2,3);
>   writeln(-1 );
> end.
>
>

faint,of course can't do it in this way...you should find a formula...


> > Can anyone of those who have solved the problem tell me
> > how ? If you use recursion 31 is a extremely enormous
> limit
> > and it works years. So a formula? How?
> I am facing the same problem. Time limite exceeding. Could
> somone advise me how to optimize the algorithm ?.program
> hanoit;
> const maxN=31;
> var i,n,nmove:integer;
>     current,target:array[1..maxN] of integer;
>
> function sama:boolean;
> var i:integer;
> begin
>   sama:=true;
>   for i:=1 to N do if current[i]<>target[i] then
>   begin
>     sama:=false;
>     exit;
>   end;
> end;
>
> procedure move(n,to_:integer);
> begin
>   inc(nmove);
>   current[n]:=to_;
>   if sama then begin writeln(nmove); readln; halt; end;
> end;
>
> procedure hanoi (n, from, to_, temp : integer);
> begin
>   if n > 0 then
>   begin
>     hanoi (n-1,from,temp,to_);
>     move(n,to_);
>     hanoi(n-1,temp,to_,from);
>   end;
> end;
> begin
>   nmove:=0;
>   read(N);
>   for i:=1 to N do
>   begin
>     read(target[i]);
>     current[i]:=1;
>   end;
>   if sama then begin writeln(nmove); readln; halt; end
>   else hanoi(N,1,2,3);
>   writeln(-1 );
> end.
>
>