10017 - The Never Ending Towers of Hanoi

[Lampiao]

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?

[Kamp]

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

[Stefan Pochmann]

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]

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]

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]

In my solution I stop printing after the game is solved.

With m = 0 print the initial tower configuration.

[Caesum]

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]

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]

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]

[fpmc]

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]

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]

yes I got my problem.
now it is accepted(P.E).
Why?

[efr_shovo]

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]

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]

You are right.