## 254 - Towers of Hanoi

Moderator: Board moderators

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Yes, BigInt is needed here, because m can be as large as 2^100-1.

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

I solved problem 254 in so many ways but now I can't see what's still wrong with my problem...

First I made the stupid error to move only 1 ring every time, after that I tried to move k rings (2^k-1<=m) but I was still wrong because I didn't use big numbers...

After I used big numbers (implemented with string - in Pascal) and I received TLE . . . I found that the program calculate for more then one time some of powers of 2. So finaly I precalculate the 2^k-1 powers for k=1,100. And now I receive WA...

This problem make me crazy, so pls. help me to find some tests for this program...

[pascal]
program p254;
var m,s:string;
i,n:integer;
t:array[1..3] of integer;
p:array[1..100] of string;

procedure decr(var m:string);
{ m <- m-1 }
var i,t,c:integer;
begin
t:=1; i:=length(m);
while t>0 do
begin
c:=ord(m)-ord('0')-t;
if c<0 then
c:=10-c
else
t:=0;
m:=chr(c+ord('0'));
i:=i-1;
end;
while (length(m)>0) and (m='0') do
delete(m,1,1);
end;

{m <- m-s}
var t,l1,l2,c1,c2,d,i:integer;
begin
l1:=length(m); l2:=length(s); d:=l1-l2;
t:=0;
for i:=l2 downto 1 do
begin
c1:=ord(m[i+d])-ord('0')-t;
c2:=ord(s)-ord('0');
if c1<c2 then
t:=1
else
t:=0;
m[i+d]:=chr(c1+10*t-c2+ord('0'));
end;
if t>0 then
begin
c1:=ord(m[d])-ord('0');
c1:=c1-1;
m[d]:=chr(c1+ord('0'));
end;
while (length(m)>0) and (m='0') do delete(m,1,1);
end;

procedure doila(n:integer;var s:string);
{ s <- 2^n }
var i,j,c,t:integer;
begin
s:='1';
t:=0;
for i:=1 to n do
begin
t:=0;
for j:=length(s) downto 1 do
begin
c:=ord(s[j])-ord('0');
c:=2*c+t;
s[j]:=chr(c mod 10+ord('0'));
t:=c div 10;
end;
if t>0 then
insert(chr(t+ord('0')),s,1);
end;
end;

function smaller(s,m:string):boolean;
{ =true if s<=m}
var i:integer;
begin
if length(s)<length(m) then
smaller:=true
else
if length(s)>length(m) then
smaller:=false
else
begin
smaller:=true;
for i:=1 to length(s) do
if s>m then
begin
smaller:=false;
break;
end;
end;
end;

procedure H(n,a,b,c:integer);
begin
if smaller(p[n],m) then
begin
t[a]:=t[a]-n;
t:=t+n;
end
else
begin
H(n-1,a,c,b);
if length(m)=0 then exit;
t[a]:=t[a]-1;
t:=t+1;
decr(m);
if length(m)>0 then
H(n-1,c,b,a);
end;
end;

begin
for i:=1 to 100 do
begin
doila(i,p);
decr(p);
end;
while m=' ' do
delete(m,1,1);
while not ((n=0) and (m='0')) do
begin
t:=n; t:=0; t:=0;
if n mod 2 =0 then
H(n,1,3,2)
else
H(n,1,2,3);
writeln(t,' ',t,' ',t);
while m=' ' do
delete(m,1,1);
end;
end.
[/pascal]

Thanks a lot . . .

Ilham Kurnia
New poster
Posts: 31
Joined: Sat Nov 17, 2001 2:00 am
Contact:

### A hint

Try to think bitwise. (that is, convert m to base 2 and then play with it). Try finding the link between the binary represenatation of m and the number of disks in each peg.

Best wishes and Merry Christmas to those celebrating.

Ilham

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### The Specification of problem 254.

Quite strange.

I test my program step by step, and it seems ok.

And I make sure the BigInt handled well.

However, I can't pass this problem.

One problem, should I transfer disks from peg A to peg C or peg B?

In the problem statement, it says "transfer them from peg A to one

of the other pegs".

But the solutions won't be indentical with the other.

In sample input, the problemsetter choose the data which can't

distinguish the right solution.

After submitting two type of solution, I got two wrong answer replies.

So there will be still some specification not clear or hidden.

One more problem, does the test data contain illegal input?

The legal ones should be n(wthin the range[0 100]) and

m(within the range[0 2^n-1]).

If m is more than or equal to 2^n, what should be printed?

Thanks for reading it. little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
for odd moves, take the smallest disk (number 1) from the peg where it lies to the next one in the circular sequence ABCABC for even moves, make the only possible move not involving disk 1.
This completely specificies where the tower should go, since the first move (an odd move) takes disk 1 from A to B. Think about it.

I don't think there is illegal input. My program doesn't test it and would produce nonsense if there was.

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Thanks for your reply. anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I tried to memorized all the moves but it gives tle. Is there any faster algorithm? will any1 describe shortly?? --
anupam
"Everything should be made simple, but not always simpler"

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Hello, anupam.

Memorizing all moves is much time consuming, maybe never be done,

because the most numbers of moves would be 2^100-1.

Try to solve it with your background knowledge.

The Tower of Honai tells you that moves n disks from one peg to another

needs 2^n-1 steps.

So when you get a number, dividing them into 2^a-1, 2^b-1, 2^c-1, and

so on.(a>b>c>....)

But for better speed, I divided them into 2^a, 2^b, 2^c, and so on.

Moving them in sets instead of in steps, you'll get what you want.

If you still have no idea of my method, please let me know. anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
well i misunderstood a little and fixed now. Thanks Boss.
--
Anupam
"Everything should be made simple, but not always simpler"

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### P-254

Hi, I always got WA.

Can somebody post some I/O for this problem(Towers Of Hanoi).

Please...  nesqi
New poster
Posts: 5
Joined: Thu Sep 30, 2004 4:18 pm
if n is 0, m has to be 0 since 2^0 -1 = 1 - 1 = 0

So if n is 0 the program should terminate.

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

### Test data needed

Could some merciful soul please post the result of this indata:

Code: Select all

``````3 5
64 2
8 45
100 1267650600228229401496703205375
100 1
36 23478162346434234
23 231234
80 398573924759238475987234
67 2349302402348238482342348
99 3895732987529387459237955432
88 747328293948729334241100234
0 0
``````
I get

Code: Select all

``````1 1 1
62 1 1
4 2 2
0 100 0
99 0 1
2 16 18
7 10 6
27 22 31
11 25 31
43 30 26
26 36 26
``````
and WA of course, since I'm wondering.

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

### Test data needed

- deleted -
Last edited by d91-lek on Fri Nov 18, 2005 4:48 am, edited 1 time in total.

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:
Got AC when I reversed the peg order. Example input is
not decisive in this matter. 100 1 should of course give
99 1 0 and not 99 0 1.

Correct output for the input above is:

Code: Select all

``````1 1 1
62 1 1
4 2 2
0 0 100
99 1 0
2 18 16
7 6 10
27 31 22
11 31 25
43 26 30
26 26 36
``````

ahmed hasan
New poster
Posts: 9
Joined: Fri Jan 21, 2005 5:09 pm

### 254 Why WA?

This code does not run in vc++.

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

unsigned long long A,B,C;
unsigned long long Moves;

void MoveDisks(unsigned long long n, unsigned long long *peg1, unsigned long long *peg2)
{
Moves-=(unsigned long long)pow(2,n)-1;
*peg1-=n;
*peg2+=n;
}

unsigned long long MoveStack(unsigned long long n, unsigned long long *p, unsigned long long *e, unsigned long long *t)
{
if(Moves==0) return 0;
if(Moves>=pow(2,n)-1) {MoveDisks(n,p,t);return 0;}
else
{
MoveStack(n-1,p,t,e);
if(Moves>=1)MoveDisks(1,p,t);
MoveStack(n-1,e,p,t);
}
return 0;
}

int main()
{
unsigned long long NumberOfDisks;
while(1)
{
scanf("%llu %llu",&NumberOfDisks,&Moves);
if(NumberOfDisks==0 && Moves==0) break;
A=NumberOfDisks;  B=0;   C=0;
MoveStack(NumberOfDisks,&A,&B,&C);
printf("%llu ",A);
printf("%llu ",B);
printf("%llu\n",C);
}
return 0;
}``````