101 - The Blocks Problem

[dumbledore]

Who can help me?
I got this when compiling:
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.010 seconds.

and this is my source in C:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int table[200][200];
int a,b, posa, posb, cola, colb, n, soblock[200];


void moveonto(int a,int b);
void moveover(int a,int b);
void pileonto(int a,int b);
void pileover(int a,int b);
int search(int x, int a[], int n);

/* main program */
int main()
{
scanf("%d",&n);
int i, j;
for (i=0;i<n;i++)
{
table[0]=i;
soblock=1;
}
fflush(stdin);
char s[20], *s1, *s2, *s3, *s4;
while (gets(s)!=NULL)
{
if (strcmp(s,"quit")==0) break;
s1=strtok(s," ");
a=atoi(strtok(NULL," "));
s2=strtok(NULL," ");
b=atoi(strtok(NULL," "));
if ((a>=n)||(b>=n)||(a==b)) continue;
for (cola=0;cola<n;cola++)
{
posa=search(a,table[cola],soblock[cola]);
if (posa!=-1) break;
}
for (colb=0;colb<n;colb++)
{
posb=search(b,table[colb],soblock[colb]);
if (posb!=-1) break;
}
if (cola==colb) continue;
if (strcmp(s1,"move")==0)
{
if (strcmp(s2,"onto")==0) moveonto(a,b);
else if (strcmp(s2,"over")==0) moveover(a,b);
}
else if (strcmp(s1,"pile")==0)
{
if (strcmp(s2,"onto")==0) pileonto(a,b);
else if (strcmp(s2,"over")==0) pileover(a,b);
}
}
for (i=0;i<n;i++)
{
printf("%d:",i);
for (j=0;j<soblock;j++) printf(" %d",table[j]);
printf("n");
}
return 0;
}
/* end of main program */

/* function */
/* search in an array */
int search(int x, int a[], int n)
{
int i;
for (i=0;i<n;i++) if (a==x) return i;
return -1;
}

/* delete an element in array at pos */
void del(int x, int a[], int &n)
{
int i;
for (i=search(x,a,n);i<n-1;i++) a=a[i+1];
n--;
}

/* insert a new element to an array at pos */
void insert(int x, int a[], int &n, int pos)
{
int i;
for (i=n;i>pos;i--) a=a[i-1];
a[pos]=x;
n++;
}

/* the move onto function */
void moveonto(int a, int b)
{
del(a,table[cola],soblock[cola]);
insert(a,table[colb],soblock[colb],posb+1);

}

/* the move over function */
void moveover(int a, int b)
{
del(a,table[cola],soblock[cola]);
insert(a,table[colb],soblock[colb],soblock[colb]);
}

/* the pile onto function */
void pileonto(int a, int b)
{
int temp[200], ntemp, i;
for (i=posa;i<soblock[cola];i++) temp[i-posa]=table[cola];
ntemp=soblock[cola]-posa;
soblock[cola]=posa;
for (i=0;i<ntemp;i++)
insert(temp,table[colb],soblock[colb],i+posb+1);

}

/* the pile over function */
void pileover(int a, int b)
{
int temp[200], ntemp, i;
for (i=posa;i<soblock[cola];i++) temp[i-posa]=table[cola];
ntemp=soblock[cola]-posa;
soblock[cola]=posa;
for (i=0;i<ntemp;i++)
insert(temp[i],table[colb],soblock[colb],soblock[colb]);
}

[fpnc]

This usually means that a pointer is out of range, or a matrix index is out of range. Think about the limits of the problem, the range of the input... This kind of thinks.

[ahanys]

See the problem set now it is updated. Num of buildings is now 5000 i think.

[dumbledore]

I can't understand, the problem say:
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.

So I can define table[25][25], but even when I use table[200][200], it's still out of range.

[junjieliang]

No, an array[25][25] is big enough. I suppose the person who posted the previous message about 5000 buildings was referring to problem 105.

[samuelcdf]

my program couldn't be accepted from judge.
and error is

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

24
move 9 onto 1
move 23 onto 22
pile 21 over 20
move 16 over 1
pile 8 over 6
pile 1 over 5
move 19 over 1
move 18 over 19
move 10 onto 0
move 7 over 1
move 17 over 14
pile 6 over 1
pile 5 over 6
pile 4 over 0
move 3 over 0
move 2 over 9
move 15 over 1
move 13 over 17
move 12 over 15
move 11 onto 13
pile 0 over 6
pile 14 over 5
pile 20 over 22
pile 23 over 9
move 5 over 9
move 19 onto 2
pile 3 onto 2
pile 0 onto 0
move 23 onto 14
move 5 over 22
quit

my program terminating normally
follow is my answer:
0: 0
1: 1
2: 2 3
3:
4: 4
5:
6: 6
7: 7
8: 8
9: 9
10: 10
11: 11
12: 12
13: 13
14: 14 23
15: 15
16: 16
17: 17
18: 18
19: 19
20: 20
21: 21
22: 22 5
23:

please tell me what wrong may be occur in my program...
By the way, why they don't promulgate the test data for the person who want to debug??
the program is used in any contest?? I don't think so.....

[junjieliang]

The following is the output from my accepted program:

0: 0
1: 1
2: 2
3: 3
4: 4
5:
6: 6
7: 7
8: 8
9: 9
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15
16: 16
17: 17
18: 18
19: 19
20: 20
21: 21
22: 22 5
23: 23

[Smartie]

my program seems to produce the wrong results (Wrong Answer: 101)

any idea where to get some test data for this example. tried it with the example data and the set in this thread .. both seems to work

[paulhryu]

I have this solution that seems to work... yet, it doesn't get accepted. Any ideas?

#include <iostream.h>
#include <fstream.h>
#include <string.h>

#define ins cin
#define outs cout

int blocks[30][30];
int nblocks[30];
int hashtbl[30];
int num;

void pileblocks(int dest, int sn, int smin);
void returnblocks(int n, int min);

int main() {
char syn1[10], syn2[10];
int i, j;

ins >> num;
for(i = 0; i < num; i++) {
blocks[0] = i;
nblocks = 1;
hashtbl = i;
}

for(;;) {
int pos1, pos2;

ins >> syn1;
if(strcmp(syn1, "quit") == 0) break;
ins >> i >> syn2 >> j;

if(i == j || hashtbl == hashtbl[j]) continue;

for(pos1 = 0; pos1 < nblocks[hashtbl]; pos1++)
if(blocks[hashtbl][pos1] == i) break;

for(pos2 = 0; pos2 < nblocks[hashtbl[j]]; pos2++)
if(blocks[hashtbl][pos2] == j) break;

i = hashtbl;
j = hashtbl[j];

if(strcmp(syn1, "move") == 0) {
if(strcmp(syn2, "over") == 0) {
returnblocks(i, pos1 + 1);
returnblocks(j, pos2 + 1);
pileblocks(j, i, pos1);
}
if(strcmp(syn2, "onto") == 0) {
returnblocks(i, pos1 + 1);
pileblocks(j, i, pos1);
}
}

if(strcmp(syn1, "pile") == 0) {
if(strcmp(syn2, "over") == 0) {
returnblocks(j, pos2 + 1);
pileblocks(j, i, pos1);
}
if(strcmp(syn2, "onto") == 0) {
pileblocks(j, i, pos1);
}
}
}

for(i = 0; i < num; i++) {
cout << i << ':';
for(j = 0; j < nblocks; j++)
cout << ' ' << blocks[j];
cout << endl;
}
}

void pileblocks(int dest, int sn, int smin) {
int i, j;

j = nblocks[dest];
for(i = smin; i < nblocks[sn]; i++) {
int k = blocks[sn][i];

blocks[dest][j++] = k;
hashtbl[k] = dest;
}

nblocks[dest] = j;
if(smin <= nblocks[sn])
nblocks[sn] = smin;
}

void returnblocks(int n, int min) {
int i;

for(i = min; i < nblocks[n]; i++) {
int k = blocks[n][i];

blocks[k][0] = k;
hashtbl[k] = k;
nblocks[k] = 1;
}

if(min <= nblocks[n])
nblocks[n] = min;
}

[soyoja]

I don't know why I received "wrong answer" message.

If someone know about this problem, please some hint to give me.

Maybe I misunderstood "Pile / Move " and "onto / over " meaning??

Here is my output to my test data

Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 onto 6
pile 8 over 5
move 2 over 1
move 4 over 9
pile 8 onto 6
pile 8 onto 5
move 2 over 3
move 4 onto 4
pile 8 over 5
pile 8 onto 6
move 2 over 2
move 4 over 9
quit

Output

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

Please Help me... If Someone have accepted

source code, please test above data and tell me the result.

Ah.. and here is my source code. Please help me


//@BEGIN_OF_SOURCE_CODE

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <string.h>

void main()
{
ofstream Outfile;
Outfile.open("101.out");

int iaBuffer[25], iaBlock[25][25];
int a, b, c,iNum, iFirst, iSecond, iTmp1, iTmp2;

char caCom[5] = {'',};

for( a = 0; a < 25; a++ )
{
iaBuffer[a] = -1;
for( b = 0; b < 25; b++ )
iaBlock[a] = -1;
}

cin >> iNum;
for( a = 0; a < iNum; a++ ) iaBlock[a][0] = a;

while( 1 )
{
c = 0;
cin >> caCom;
if( strcmp(caCom,"quit") == 0 ) break;

if( strcmp(caCom,"move") == 0 )
{
cin >> iFirst;

for( a = 0; a < iNum; a++ )
for( b = 0; b < 25; b++ )
{
if( iaBlock[a] == iFirst )
{
iaBlock[a] = -1;
// init stacked iFirst block
if( iaBlock[a][b+1] != -1 )
while( b < 25 && iaBlock[a][b+1] != -1 )
iaBlock[iaBlock[a][b+1]][0] = iaBlock[a][b+1],
iaBlock[a][b+1] =-1, b++;
else break;
}
}

cin >> caCom;
if( strcmp(caCom,"onto") == 0 )
{
cin >> iSecond;
for( a = 0; a < iNum; a++ )
{
for( b = 0; b < 25; b++ )
{
if( iaBlock[a] == iSecond )
{
iTmp1 = a, iTmp2 = b+1;
// init stacked iFirst block
if( iaBlock[a][b+1] != -1 )
{
while( b < 25 && iaBlock[a][b+1] != -1 )
iaBlock[iaBlock[a][b+1]][0] = iaBlock[a][b+1],
iaBlock[a][b+1] =-1, b++;
}
}
}
}
iaBlock[iTmp1][iTmp2] = iFirst;
}
else if( strcmp(caCom,"over") == 0 )
{
cin >> iSecond;
for( a = 0; a < iNum; a++ )
for( b = 0; b < 25; b++ )
{
if( iaBlock[a] == iSecond )
{
while( b < 25 && iaBlock[a] != -1 ) b++;
iTmp1 = a, iTmp2 = b;
}
}
iaBlock[iTmp1][iTmp2] = iFirst;
}
}
else if( strcmp(caCom,"pile") == 0 )
{
cin >> iFirst;
for( a = 0; a < iNum; a++ )
for( b = 0; b < 25; b++ )
if( iaBlock[a] == iFirst )
{
while( b < 25 && iaBlock[a] != -1 )
iaBuffer[c] = iaBlock[a], iaBlock[a] =-1, b++, c++;
break;
}

cin >> caCom;
if( strcmp(caCom,"onto") == 0 )
{
cin >> iSecond;
for( a = 0; a < iNum; a++ )
for( b = 0; b < 25; b++ )
{
if( iaBlock[a][b] == iSecond )
{
iTmp1 = a, iTmp2 = b+1;
// init stacked iFirst block
if( iaBlock[a][b+1] != -1 )
{
while( b < 25 && iaBlock[a][b+1] != -1 )
iaBlock[iaBlock[a][b+1]][0] = iaBlock[a][b+1],
iaBlock[a][b+1] =-1, b++;
}
}
}
for( a = 0; a < c; a++ )
iaBlock[iTmp1][iTmp2+a] = iaBuffer[a];
}
else if( strcmp(caCom,"over") == 0 )
{
cin >> iSecond;
for( a = 0; a < iNum; a++ )
for( b = 0; b < 25; b++ )
{
if( iaBlock[a][b] == iSecond )
{
while( b < 25 && iaBlock[a][b] != -1 ) b++;
iTmp1 = a, iTmp2 = b;
}
}
for( a = 0; a < c; a++ )
iaBlock[iTmp1][iTmp2+a] = iaBuffer[a];
}
}
}

// output
for( a = 0; a < iNum; a++ )
{
Outfile << a << ":";
for( b = 0; b < iNum; b++ )
{
if( iaBlock[a][b] == -1 ) continue;
Outfile << " " << iaBlock[a][b];
}
Outfile << endl;
}
}

//@END_OF_SOURCE_CODE

[Adrian Kuegel]

Your Output is wrong. The correct output is:
0: 0
1: 1 9 4
2:
3: 3 2
4:
5: 5 8 7 6
6:
7:
8:
9:

[C8H10N4O2]

Here is the distinctions in the commands.
Move returns the blocks on top of the FIRST argument to their original spots while Pile does not. Onto returns the blocks on top of the SECOND argument to their original spots while Over does not.

[William]

Simple question:

let start-configuration:

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

whats next configuration after
move 1 over 3
is it:
a)
0: 0 1
1:
2: 2
3: 3
4: 4
5: 5

or
b)
0: 0
1:
2: 2
3: 3 1
4: 4
5: 5
???
so the question is:
first remove all blocks stacked on 1 and then put 1 on the block with 3 AFTER it has been returned to initial position
or
put it on the block it was BEFORE it has been returned to initial position ?

Thanks alot for helping !

[Ivor]

I can't quite remember atm, but shouldn't you ignore all commands where a == b or a and b are in the same stack?

Ivor

[cyfra]

Hi!

First return all the blocks that are on the block a onto their initial positions (if there is a block nr. 10 - you put on the top of the 10'th stack)
then you put a on the b stack...

that's all...

I hope it will help..

Good Luck