OJ Board

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?

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

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!

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.

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

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

With m = 0 print the initial tower configuration.

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..........

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]

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

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?

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

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?

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?

You are right.