101 - The Blocks Problem

Max Fate · Post by **Max Fate** » Mon Mar 18, 2002 10:41 pm

Since a and b are in the same stack (0) this command should be ignored
So configuration will not change:

0: 0 1 2 3 4 5
1:
2:
3:
4:
5:

tsaiid · Post by **tsaiid** » Sun Jun 02, 2002 5:48 pm

I have a question that if the original is set like this:

0: 0
1: 7 3 1 4 2
2:
3:
4:
5: 5
6: 6
7:

now if I input "pile 3 over 2", what's the result!?

thanks for your help.

Stefan Pochmann · Post by **Stefan Pochmann** » Sun Jun 02, 2002 11:36 pm

Read the problem, it says "illegal commands should be ignored".

tsaiid · Post by **tsaiid** » Mon Jun 03, 2002 4:32 pm

I think the problem might be in the main function, but I don't
know exactly where the mistake I made. This is the messages
that the judge sent back:

Your program has used more time (30.090 seconds) than the maximum allowed for this problem by this judge (30 seconds).

and below is my source code.

#include <stdio.h>

struct block
{
int num;
struct block *next;
};

int x;
struct block serial[25], b[25];

static struct block *
search (tgt, mode)
int tgt;
int mode;
{
register int n;
struct block *tmp;

if (mode > 0) /* for "onto" */
{
if (!serial[tgt].next)
return &serial[tgt];
else
{
tmp = serial[tgt].next;
while (tmp->next)
{
tmp = tmp->next;
}
return tmp;
}
}
else if (mode == -1)
{
for (n = 0; n < x; n++)
{
if (serial[n].next == &b[tgt])
return &serial[n];
}
for (n = 0; n < x; n++)
{
if (b[n].next == &b[tgt])
return &b[n];
}
}
else /* for "over" */
{
tmp = &b[tgt];
while (tmp->next)
tmp = tmp->next;
return tmp;
}

return NULL;
}

static void
move (src, dst, mode)
int src;
int dst;
int mode;
{
struct block *dstb, *dstb2;
if (mode)
{
dstb = &serial[dst];
while (dstb->next)
{
if (dstb->next == &b[src])
return;
else
dstb = dstb->next;
}
}
while (1)
{
dstb = search(src, 0);
if (dstb == &b[src])
break;
dstb2 = search(dstb->num, -1);
dstb2->next = NULL;
dstb2 = search(dstb->num, 1);
dstb2->next = dstb;
}

if (mode) /* for "onto" */
{
dstb = search(src, -1);
dstb->next = NULL;
dstb = search(dst, 1);
dstb->next = &b[src];
}
else /* for "over" */
{
dstb = &b[src];
while (dstb->next)
{
if (dstb->next == &b[dst])
return;
else
dstb = dstb->next;
}

dstb = &b[dst];
while (dstb->next)
{
if (dstb->next == &b[src])
return;
else
dstb = dstb->next;
}
dstb = search(src, -1);
dstb->next = NULL;
dstb = search(dst, 0);
dstb->next = &b[src];
b[src].next = NULL;
}
}

static void
pile (src, dst, mode)
int src;
int dst;
int mode;
{
struct block *dstb, *dstb2;
if (mode) /* for "onto" */
{
dstb = &serial[dst];
while (dstb->next)
{
if (dstb->next == &b[src])
return;
else
dstb = dstb->next;
}

while (1)
{
dstb = search(dst, 1);
if (dstb == &b[dst])
{
if ((dstb2 = search(dst, -1)) == &serial[dst])
break;
}
else if (dstb == &serial[dst])
break;
dstb2 = search(dstb->num, -1);
dstb2->next = NULL;
dstb2 = search(dstb->num, 1);
dstb2->next = dstb;
}

dstb = search(src, -1);
dstb->next = NULL;
dstb = search(dst, 1);
dstb->next = &b[src];
}
else /* for "over" */
{
dstb = &b[src];
while (dstb->next)
{
if (dstb->next == &b[dst])
return;
else
dstb = dstb->next;
}
dstb = &b[dst];
while (dstb->next)
{
if (dstb->next == &b[src])
return;
else
dstb = dstb->next;
}
dstb = search(src, -1);
dstb->next = NULL;
dstb = search(dst, 0);
dstb->next = &b[src];
}
}

int
main(void)
{
int src, dst, mode;
register int n;
char buf[10], string[40];
struct block *tmp;

buf[0] = '\0';
memset(string, 0, sizeof(string));
memset(b, 0, sizeof(struct block) * 25);
memset(serial, 0, sizeof(struct block) * 25);

fgets(buf, sizeof(buf), stdin);
if ((x = atoi(buf)) > 24 || x < 1)
exit(1);
for (n = 0; n < x; n++)
{
b[n].num = serial[n].num = n;
b[n].next = NULL;
serial[n].next = &b[n];
}

while (1)
{
char *cmd[8], *p, *head;
int n;

p = fgets(string, sizeof(string), stdin);

if (!strncmp(p, "quit", 4))
break;
memset(cmd, 0, sizeof(cmd));
head = NULL;
for (n = 0; *p != '\n'; p++)
{
if (!head && *p != ' ')
{
head = p;
}

if (head)
{
if (*p == ' ')
{
(int) cmd[n] = malloc(30 * sizeof(char));
strncpy(cmd[n++], head, p - head);
head = NULL;
}
if (*(p + 1) == '\n')
{
(int) cmd[n] = malloc(30 * sizeof(char));
strncpy(cmd[n++], head, p - head + 1);
head = NULL;
}
}
}
mode = strcmp(cmd[2], "over") ? 1 : 0; /* 1: onto 0: over */
if ((src = atoi(cmd[1])) == (dst = atoi(cmd[3])))
continue; /* illegal command */

strstr(string, "move") ? move(src, dst, mode) : pile(src, dst, mode);
}
for (n = 0; n < x; n++)
{
printf("%d: ", n);
tmp = serial[n].next;
while (tmp)
{
printf("%d ", tmp->num);
tmp = tmp->next;
}
puts("");
}

return 0;
}

and I have one more question.
if the original is set like this:

0: 0 1 7 4 2
1:
2: 3 5
3:
4:
5:
6: 6
7:
8: 8

and then i excute command: "move 1 onto 2"

is the result like :

0: 0
1:
2: 3 5 2 1
3:
4: 4
5:
6: 6
7: 7
8: 8

or

0: 0
1:
2: 2 1
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8

thanks for your help!!

Stefan Pochmann · Post by **Stefan Pochmann** » Tue Jun 04, 2002 7:27 am

About your example at the end: Neither nor. I repeat:

Read the problem, it says "illegal commands should be ignored".

tsaiid · Post by **tsaiid** » Tue Jun 04, 2002 1:14 pm

sorry...I haven't noticed that block 1 & 2 are in the same stack.

the example I made is a bad one. but what I did want to know is

if the original is set like:

0: 0 1 7 4
1:
2:
3: 2
4: 3 5
5:
6: 6
7:
8: 8

and then execute "move 1 onto 2", what's the result?

0: 0
1:
2: 1
3: 2
4: 3 5 4
5:
6: 6
7: 7
8: 8

or

0: 0
1:
2: 2 1
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8

or something....
the difference between the two results above is
we would like to return blocks above block 1 to their initial positions.
what does "initial position" mean? and if there are some other blocks
on their initial positions, do I have to return them!?
thanks.

Stefan Pochmann · Post by **Stefan Pochmann** » Wed Jun 05, 2002 6:49 am

It's been a while since I solved it but I believe (after reading the problem and my solution) that the first of your two alternatives is correct.

Betovsky · Post by **Betovsky** » Wed Jun 05, 2002 7:35 pm

I think that is none of u said

if the original set is like:

0: 0 1 7 4
1:
2:
3: 2
...

and the comando is move 1 onto 2

i think the result would be:

0: 0
1:
2:
3: 2 1
...

i think it counts the place its the box 2... not the position 2 of the table.
at least is what i think, cause in the example move 4 over 9
the 4 goes to the pile of position 1 not to the position 9
...

tsaiid · Post by **tsaiid** » Wed Jun 05, 2002 9:47 pm

Thanks for your help....
Now I think I knew all the rules,
but I don't know why the Judge replied a "Time Limit Exceeded."
Could anyone tell me in what situation will get this result?
Thanks again.

Stefan Pochmann · Post by **Stefan Pochmann** » Wed Jun 05, 2002 10:36 pm

I'd guess that you have a bug somewhere that causes an infinite loop. I think the problem shoudln't time out even with a total brute force method when you do it right.

SilentStrike · Post by **SilentStrike** » Thu Jun 20, 2002 1:33 pm

I just completed 101. Got it first shot (unless you count putting the field as 100 in the judge ID.. just copied from my last problem)

. It was a lot of code for a "simple" problem though.

My solution is 150 lines and 3.8k. Anyone have a smaller solution? What is the "elegant" way of solving that problem?

Stefan Pochmann · Post by **Stefan Pochmann** » Thu Jun 20, 2002 8:08 pm

Don't know how good this is compared to others, but I have several programs of about 50 lines, using doubly-linked lists and recursive functions that are used for different purposes, if I remember right.

taj79 · Post by **taj79** » Sat Jun 22, 2002 2:34 pm

main()
{ char s[50];
int n;

scanf("%s",s);
n= atoi(s);
printf("%d\n",n);

scanf("%[^\n]",s);
printf("%s\n",s);
scanf("%[^\n]",s);
printf("%s\n",s);
}

If my input file is
10
move 9 onto 1
move 8 over 1
move 7 over 1

The output is
10
10
10

Why is it unable to read the 2nd line.

10153EN · Post by **10153EN** » Sat Jun 22, 2002 3:56 pm

I think you want to read in the whole line. Why not using gets(s)?

P.S. Please be considerate and post your question in the respective thread.

I can see there's a thread about problem 101 just somewhere below *your* thread.

taj79 · Post by **taj79** » Tue Jun 25, 2002 2:48 pm

I have submitted the prog and the judge says: Runtime Error
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.000 seconds.

I have runned my prog in my computer and its OK i think

Code: Select all

[c]
            #include<stdio.h> 
            #include<stdlib.h> 
            #include<string.h> 

            #define MAX 25 

            void func1(int A[][MAX],int B[],int S[],int a,int b,int n); 
            void func2(int A[][MAX],int B[],int S[],int a,int b,int n); 
            void func3(int A[][MAX],int B[],int S[],int a,int b,int n); 
            void func4(int A[][MAX],int B[],int S[],int a,int b,int n); 
            void output(int A[][MAX],int S[],int n); 

            main() 
            {int n,t,c,d,e,f,g,h,a,b,n1,t1=0,i; 
            char s[50],s1[50]; 
            int A[MAX][MAX],B[MAX],S[MAX]; 

            /* scanf("%s",s3); 
            s[strlen(s)+1]='\0'; 
            n= atoi(s3); 
            printf("%d\n",n); */ 

            gets(s); 
            n= atoi(s); 
            /* printf("%d\n",n); */ 

            /* Initilaizing the blocks */ 
            for(i=0;i<n;i++) 
            { 
            A[i][0] = i; 
            B[i]= i;/* This shows the position of iTH block above which base it is*/ 
            S[i]=0;/* This shows the top pos of the stack */ 
            } 



            do{ t1=0; 
            gets(s); 
            /*scanf("%[^\n]",s); 
            s[strlen(s)+1]='\0'; */ 

            /* printf("%s\n",s); */ 
            if( strcmp(s,"quit") == 0 ) 
            { output(A,S,n); 
            exit(1); 
            } 

            t=0; 
            /* printf("\n%c ",s[t]); */ 
            while(s[t] != ' ') 
            ++t; 
            /* printf("%c ",s[t-1]); */ 
            while(s[t] == ' ') 
            ++t; 
            c=t; 
            while(s[t] != ' ') 
            ++t; 
            d=t-1; 
            while(s[t] == ' ') 
            ++t; 
            e=t; 
            /* printf("%c ",s[t]); */ 
            while(s[t] != ' ') 
            ++t; 
            f=t; 
            /* printf("%c ",s[t-1]); */ 
            while(s[t] == ' ') 
            ++t; 
            g=t; 
            while(s[t] != '\n') 
            ++t; 
            h=t-1; 

            n1=c; 
            while(n1<=d) 
            { s1[n1-c]= s[n1]; 
            ++n1; 
            } 
            s1[n1]='\0'; 
            a = atoi(s1);/*takes the 1st int as a */ 
            /* printf("\n a = %d",a); */ 
            n1=g; 
            while(n1<=h) 
            { s1[n1-g]= s[n1]; 
            ++n1; 
            } 
            s1[n1]='\0'; 
            b = atoi(s1);/*takes the 2nd int as b */ 
            /* printf(" b=%d\n",b); */ 

            if(s[0] == 'm' && s[e+1]== 'n' ) 
            func1(A,B,S,a,b,n); 
            if(s[0] == 'm' && s[e+1]== 'v' ) 
            func2(A,B,S,a,b,n); 
            if(s[0] == 'p' && s[e+1]== 'n' ) 
            func3(A,B,S,a,b,n); 
            if(s[0] == 'p' && s[e+1]== 'v' ) 
            func4(A,B,S,a,b,n); 


            }while( strcmp(s,"quit") ); 

            } 

            void func1(int A[][MAX],int B[],int S[],int a,int b,int n) 
            {int base_a,base_b,num_at_top; 
            /* printf("1\n"); */ 
            if(a==b || B[a] == B[b]) 
            return; 
            base_a=B[a]; 
            base_b=B[b]; 
            while( A[base_a][S[base_a]] != a) 
            { 
            num_at_top = A[base_a][S[base_a]]; 
            --S[base_a]; 
            B[num_at_top] = num_at_top; 
            ++S[num_at_top]; 
            A[num_at_top][S[num_at_top]] = num_at_top; 
            } 

            while( A[base_b][S[base_b]] != b) 
            { 
            num_at_top = A[base_b][S[base_b]]; 
            --S[base_b]; 
            B[num_at_top] = num_at_top; 
            ++S[num_at_top]; 
            A[num_at_top][S[num_at_top]] = num_at_top; 
            } 

            B[a]= B[b]; 
            --S[base_a]; 
            ++S[base_b]; 
            A[base_b][S[base_b] ] = a; 

            return; 
            } 



            void func2(int A[][MAX],int B[],int S[],int a,int b,int n) 
            { int base_a,base_b,num_at_top; 
            /* printf("2\n"); */ 

            if(a==b || B[a] == B[b]) 
            return; 
            base_a=B[a]; 
            base_b=B[b]; 
            while( A[base_a][S[base_a]] != a) 
            { 
            num_at_top = A[base_a][S[base_a]]; 
            --S[base_a]; 
            B[num_at_top] = num_at_top; 
            ++S[num_at_top]; 
            A[num_at_top][S[num_at_top]] = num_at_top; 
            } 

            B[a]= B[b]; 
            --S[base_a]; 
            ++S[base_b]; 
            A[base_b][S[base_b] ] = a; 

            return; 
            } 

            void func3(int A[][MAX],int B[],int S[],int a,int b,int n) 
            { int base_a,base_b,num_at_top; 
            int temp[MAX],temp_count= -1; 

            /* printf("3\n"); */ 
            if(a==b || B[a] == B[b]) 
            return; 
            base_a=B[a]; 
            base_b=B[b]; 
            /* removing all the blocks above b */ 
            while( A[base_b][S[base_b]] != b) 
            { 
            num_at_top = A[base_b][S[base_b]]; 
            --S[base_b]; 
            B[num_at_top] = num_at_top; 
            ++S[num_at_top]; 
            A[num_at_top][S[num_at_top]] = num_at_top; 
            } 

            /* removing all the blocks above a and a also to a temp array so that the order for 
            putting them above b remains as it was in original */ 
            do{ 
            temp[++temp_count] = A[base_a][S[base_a]]; 
            --S[base_a]; 
            }while( temp[temp_count] != a); 

            /* emptying temp array and putting the blocks over b*/ 
            do{ 
            A[base_b][++S[base_b]]= temp[temp_count]; 
            B[ temp[temp_count] ] = base_b; 
            --temp_count; 
            }while(temp_count > -1 ); 

            return; 

            } 

            void func4(int A[][MAX],int B[],int S[],int a,int b,int n) 
            { int base_a,base_b,num_at_top; 
            int temp[MAX],temp_count= -1; 

            /* printf("4\n"); */ 
            if(a==b || B[a] == B[b]) 
            return; 
            base_a=B[a]; 
            base_b=B[b]; 

            /* removing all the blocks above a and a also to a temp array so that the order for 
            putting them above b remains as it was in original */ 
            do{ 
            temp[++temp_count] = A[base_a][S[base_a]]; 
            --S[base_a]; 
            }while(temp[temp_count] != a); 

            /* emptying temp array and putting the blocks over b*/ 
            do{ 
            A[base_b][++S[base_b]]= temp[temp_count]; 
            B[ temp[temp_count] ] = base_b; 
            --temp_count; 
            }while(temp_count > -1 ); 

            return; 


            } 


            void output(int A[][MAX],int S[],int n) 
            { int i,j,num_blocks; 
            for(i=0;i<n;i++) 
            { 
            printf("\n%d:",i); 
            if(S[i] == -1) 
            continue; 
            num_blocks = S[i];/* gives the top of the stack */ 
            for(j=0;j<=num_blocks;j++) 
            printf(" %d",A[i][j] ); 
            } 
            printf("\n"); 
            return; 
            } 

[/c]

Please run it on your computer and tell me if there's any prob
I can't find any difficulty in running

Code: Select all

OJ Board

101 - The Blocks Problem

101 - The Blocks Problem

I got Time Limit Exceeded.

Prob 101 My prog is unable to read input strings properly