## 101 - The Blocks Problem

Moderator: Board moderators

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am
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
New poster
Posts: 4
Joined: Sun Jun 02, 2002 5:43 pm

### 101 - The Blocks Problem

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!?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Read the problem, it says "illegal commands should be ignored".

tsaiid
New poster
Posts: 4
Joined: Sun Jun 02, 2002 5:43 pm

### I got Time Limit Exceeded.

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, b;

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, string;
struct block *tmp;

buf = '\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)
{
int n;

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

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

{
if (*p == ' ')
{
(int) cmd[n] = malloc(30 * sizeof(char));
}
if (*(p + 1) == '\n')
{
(int) cmd[n] = malloc(30 * sizeof(char));
}
}
}
mode = strcmp(cmd, "over") ? 1 : 0; /* 1: onto 0: over */
if ((src = atoi(cmd)) == (dst = atoi(cmd)))
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

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

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

tsaiid
New poster
Posts: 4
Joined: Sun Jun 02, 2002 5:43 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal
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
New poster
Posts: 4
Joined: Sun Jun 02, 2002 5:43 pm
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

### Prob 101 My prog is unable to read input strings properly

main()
{ char s;
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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
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
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
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,s1;
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] = 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 == 'm' && s[e+1]== 'n' )
func1(A,B,S,a,b,n);
if(s == 'm' && s[e+1]== 'v' )
func2(A,B,S,a,b,n);
if(s == 'p' && s[e+1]== 'n' )
func3(A,B,S,a,b,n);
if(s == '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