## 10017 - The Never Ending Towers of Hanoi

Moderator: Board moderators

Lampiao
New poster
Posts: 3
Joined: Thu Nov 22, 2001 2:00 am
Location: Recife, Brazil
Contact:

### 10017 - The Never Ending Towers of Hanoi

I think there is a mistake in this problem description. Almost everyone has accepted P.E.! Including me Does anybody know what is the magic on it?
Gustavo Santos

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:
Is it possible that the number of last move is bigger then 2^n -1 ??? Because I have all the time WA Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Back in the original contest the "magic" was that they had some extra space characters here and there. At least that was the reason I didn't win it (in contests P.E.'s are not accepted) and I guess they haven't changed it yet. If you want to get "Accepted", look at the html src on how to set spaces.

Once more, I suggest that in online contests, P.E.'s are accepted, just like in the problemset...

Or make the problem setters who screw the data pay for it!

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am
Hi !
I'm so interested in this problem. But I don't understand how it can be solved efficiently. Pls inform me about it.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
so if the moves are completed before m moves are made do you stop and go on to the next, or do you carry on printing completed boards or do you carry on moving pieces back and forth ?
what about when m=0 ? presumably you just output the board and move on to the next ?

ive had about 15 wa's on this and cant really see why at all AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:
In my solution I stop printing after the game is solved.

With m = 0 print the initial tower configuration.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
some of my outputs:
Problem #3

A=> 1
B=>
C=>

A=>
B=>
C=> 1
Problem #4

A=> 2 1
B=>
C=>

A=> 2
B=> 1
C=>

A=>
B=> 1
C=> 2

A=>
B=>
C=> 2 1
Problem #5

A=> 3 2 1
B=>
C=>

A=> 3 2
B=>
C=> 1

A=> 3
B=> 2
C=> 1

A=> 3
B=> 2 1
C=>

A=>
B=> 2 1
C=> 3

A=> 1
B=> 2
C=> 3

A=> 1
B=>
C=> 3 2

A=>
B=>
C=> 3 2 1
and i am still WA btw..........

Manuel FM
New poster
Posts: 1
Joined: Sun Oct 20, 2002 4:59 pm

### any sugestions?

I've tried about everything I can think of, but I keep receiving WAs.

- The program has correctly formatted output: diff expected.txt mine.txt doesn't locate differences, where "expected" is pasted from the web, and "mine" is generated using the web's example input.

- The program gives correct answers for
1 100
...
6 100
and ends a testcase once it has already been solved.

- Odd disk numbers are correctly placed on stack "C".

what else should I check?
any newlines/spaces I may have missed? (that is, that are not present in web's example output).

[/code]

yan4546
New poster
Posts: 7
Joined: Fri Nov 15, 2002 4:17 am
Contact:

### 10017

I have tried many ways to solve the problem 10017.but I always get the wrong answer.
Who can tell me why???

Is there anyone who has got accepted be willing to show me the codes?
Thank you!
Email: yan4546@eyou.com            [/cpp]
aaaaaaaaaaaaaaaaaaaaa

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm
Hi,
Some pointers:

1) The sample output is wrong here. The first ouput case for 64 2 is wrong, which probably most people have noticed without asking.

2) Just in case you're using the iterative algorithm, be careful when n is odd. For n odd, you have to move the smallest disk 'counter-clockwise' in order for the end result to be on peg C.

3) When m > 2^n-1 (ie. when the configuration is done but input still asks you to continue), just keep on printing the final configuration.

Hope it helps,
Frank

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 10017 gives Output limite exite Why?

here is my code.

#include<stdio.h>

long n,m,i,j,m1;
int a,b,c,top=-1,top1=-1,u;

void move(long n1,int a2,int b2,int c2);
void print(int a1[],int b1[],int c1[]);
void babul2(int a4[],int n3);

void main()
{
while(1)
{
scanf("%ld %ld",&n,&m);
m1=m;
if(n<=0&&n>1250&&m<0&&m>65536)
break;
u++;
for(i=n;i>0;i--)
{
a[j]=i;
j++;
}
j--;
printf("Problem#%d\n\n\n",u);
print(a,b,c);
move(n,1,3,2);
j=0;
top=-1;
top1=-1;
}
}

void print(int a1[],int b1[],int c1[])
{
printf("A=> ");
for(int i=0;i<=j;i++)
{
printf("%d ",a1);
}
printf("\n");
printf("B=> ");
for(i=0;i<=top ;i++)
{
printf("%d ",b1);
}
printf("\n");
printf("C=> ");
for(i=0;i<=top1 ;i++)
{
printf("%d ",c1);
}
printf("\n\n");
}

void move(long n1,int a2,int b2,int c2)
{
if(n1>0)
{
move(n1-1,a2,c2,b2);
m--;
if(m<0)
n1=0;
else
{
if(a2==1&&b2==2)
{
top++;
b[top]=a[j];
j--;
babul2(b,top);
print(a,b,c);
}
if(a2==1&&b2==3)
{
top1++;
c[top1]=a[j];
j--;
babul2(c,top1);
print(a,b,c);
}
if(a2==2&&b2==3)
{
top1++;
c[top1]=b[top];
top--;
babul2(c,top1);
print(a,b,c);
}
if(a2==2&&b2==1)
{
j++;
a[j]=b[top];
top--;
babul2(a,j);
print(a,b,c);
}
if(a2==3&&b2==2)
{
top++;
b[top]=c[top1];
top1--;
babul2(b,top);
print(a,b,c);
}
if(a2==3&&b2==1)
{
j++;
a[j]=c[top1];
top1--;
babul2(a,j);
print(a,b,c);
}
move(n1-1,c2,b2,a2);
}
}
}

void babul2(int a4[],int n3)
{
int k=0,temp=0,ptr=0;
for(k=0;k<=n3-1;k++)
{
ptr=0;
while(ptr<n3-k)
{
if(a4[ptr]<a4[ptr+1])
{
temp=a4[ptr];
a4[ptr]=a4[ptr+1];
a4[ptr+1]=temp;
}
ptr++;
}
}
}

10017 gives Output limite exite Why?

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am
yes I got my problem.
now it is accepted(P.E).
Why?

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 10017 Why gives P.E

here is my code.

#include<stdio.h>

long n,m,i,j,m1;
int a,b,c,top=-1,top1=-1,u;

void move(long n1,int a2,int b2,int c2);
void print(int a1[],int b1[],int c1[]);
void babul2(int a4[],int n3);

void main()
{
while(1)
{
scanf("%ld %ld",&n,&m);
m1=m;
if(n==0&&m==0)
break;
u++;
for(i=n;i>0;i--)
{
a[j]=i;
j++;
}
j--;
printf("Problem#%d\n\n\n",u);
print(a,b,c);
move(n,1,3,2);
j=0;
top=-1;
top1=-1;
}
}

void print(int a1[],int b1[],int c1[])
{
printf("A=> ");
for(int i=0;i<=j;i++)
{
printf("%d ",a1);
}
printf("\n");
printf("B=> ");
for(i=0;i<=top ;i++)
{
printf("%d ",b1);
}
printf("\n");
printf("C=> ");
for(i=0;i<=top1 ;i++)
{
printf("%d ",c1);
}
printf("\n\n");
}

void move(long n1,int a2,int b2,int c2)
{
if(n1>0)
{
move(n1-1,a2,c2,b2);
m--;
if(m<0)
n1=0;
else
{
if(a2==1&&b2==2)
{
top++;
b[top]=a[j];
j--;
babul2(b,top);
print(a,b,c);
}
if(a2==1&&b2==3)
{
top1++;
c[top1]=a[j];
j--;
babul2(c,top1);
print(a,b,c);
}
if(a2==2&&b2==3)
{
top1++;
c[top1]=b[top];
top--;
babul2(c,top1);
print(a,b,c);
}
if(a2==2&&b2==1)
{
j++;
a[j]=b[top];
top--;
babul2(a,j);
print(a,b,c);
}
if(a2==3&&b2==2)
{
top++;
b[top]=c[top1];
top1--;
babul2(b,top);
print(a,b,c);
}
if(a2==3&&b2==1)
{
j++;
a[j]=c[top1];
top1--;
babul2(a,j);
print(a,b,c);
}
move(n1-1,c2,b2,a2);
}
}
}

void babul2(int a4[],int n3)
{
int k=0,temp=0,ptr=0;
for(k=0;k<=n3-1;k++)
{
ptr=0;
while(ptr<n3-k)
{
if(a4[ptr]<a4[ptr+1])
{
temp=a4[ptr];
a4[ptr]=a4[ptr+1];
a4[ptr+1]=temp;
}
ptr++;
}
}
}

10017 gives Output limite exite Why?

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:

### 10017 - Isn't the output wrong?

Hi!
I think that the sample output for problem#1 is wrong. It seems that on the first move it just removes a disk from A and doesn't put it anywhere. Am I right?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You are right.