254 - Towers of Hanoi

[cytse]

Yes, BigInt is needed here, because m can be as large as 2^100-1.

[pc5971]

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[1]='0') do
delete(m,1,1);
end;


procedure scad(var m,s:string);
{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[1]='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;
scad(m,p[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;
readln(n,m);
while m[1]=' ' do
delete(m,1,1);
while not ((n=0) and (m[1]='0')) do
begin
t[1]:=n; t[2]:=0; t[3]:=0;
if n mod 2 =0 then
H(n,1,3,2)
else
H(n,1,2,3);
writeln(t[1],' ',t[2],' ',t[3]);
readln(n,m);
while m[1]=' ' do
delete(m,1,1);
end;
end.
[/pascal]

Thanks a lot . . .

[Ilham Kurnia]

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]

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]

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]

Thanks for your reply.

[anupam]

I tried to memorized all the moves but it gives tle. Is there any faster algorithm? will any1 describe shortly??
--
anupam

[Ghost77 dimen]

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]

well i misunderstood a little and fixed now. Thanks Boss.
--
Anupam

[Red Scorpion]

Hi, I always got WA.

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

Please...

[nesqi]

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]

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]

- deleted -

[d91-lek]

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]

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