10017 - The Never Ending Towers of Hanoi

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by Lampiao » Mon Dec 03, 2001 9:46 pm

I think there is a mistake in this problem description. Almost everyone has accepted P.E.! Including me :smile:
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:

Post by Kamp » Thu Mar 28, 2002 5:24 pm

Is it possible that the number of last move is bigger then 2^n -1 ??? Because I have all the time WA :sad:

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Fri Mar 29, 2002 6:42 pm

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

Post by chang » Fri Apr 05, 2002 3:44 pm

Hi !
I'm so interested in this problem. But I don't understand how it can be solved efficiently. Pls inform me about it.
Thanks in advance.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sat Jul 20, 2002 3:38 pm

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 :cry:

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Sun Jul 21, 2002 9:46 pm

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:

Post by Caesum » Thu Jul 25, 2002 6:37 pm

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?

Post by Manuel FM » Sun Oct 20, 2002 5:08 pm

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

Post by yan4546 » Sat Nov 16, 2002 11:22 am


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
:roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll: :roll: [/cpp]
aaaaaaaaaaaaaaaaaaaaa

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

Post by fpmc » Thu Aug 26, 2004 12:54 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?

Post by efr_shovo » Wed Sep 29, 2004 9:47 am

here is my code.


#include<stdio.h>

long n,m,i,j,m1;
int a[10000],b[10000],c[10000],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

Post by efr_shovo » Wed Oct 06, 2004 8:42 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

Post by efr_shovo » Wed Oct 06, 2004 8:50 am

here is my code.


#include<stdio.h>

long n,m,i,j,m1;
int a[10000],b[10000],c[10000],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?

Post by Lord Nemrod » Sun Apr 17, 2005 9:24 am

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Apr 17, 2005 10:29 am

You are right.

Post Reply

Return to “Volume 100 (10000-10099)”