101 - The Blocks Problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
dumbledore
New poster
Posts: 2
Joined: Mon Nov 12, 2001 2:00 am
Location: Vietnam
Contact:

Post by dumbledore » Mon Nov 12, 2001 4:44 pm

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
System administrator
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am
Location: Valladolid, Spain

Post by fpnc » Sat Nov 24, 2001 10:18 pm

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
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Post by ahanys » Mon Nov 26, 2001 12:56 pm

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

dumbledore
New poster
Posts: 2
Joined: Mon Nov 12, 2001 2:00 am
Location: Vietnam
Contact:

Post by dumbledore » Mon Nov 26, 2001 6:37 pm

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Tue Nov 27, 2001 5:53 am

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
New poster
Posts: 3
Joined: Tue Dec 04, 2001 2:00 am
Contact:

Post by samuelcdf » Tue Dec 04, 2001 7:14 pm

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Fri Dec 07, 2001 10:41 am

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
New poster
Posts: 1
Joined: Wed Jan 02, 2002 2:00 am

Post by Smartie » Wed Jan 02, 2002 4:43 pm

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
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Sat Jan 26, 2002 3:23 am

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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Sun Feb 17, 2002 5:21 pm

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 :smile:


//@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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Feb 18, 2002 1:58 am

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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Feb 28, 2002 12:22 am

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
New poster
Posts: 2
Joined: Tue Mar 05, 2002 2:00 am
Contact:

Post by William » Sun Mar 10, 2002 3:07 am

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Mar 10, 2002 1:18 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Mon Mar 18, 2002 4:03 pm

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 :smile:

Post Reply

Return to “Volume 1 (100-199)”