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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

Thanks for your helping of debuging. I got AC. And I'll change my way of asking questions.

How-Yun Yin
New poster
Posts: 3
Joined: Sun Aug 04, 2002 11:00 am

p101....I don't know why i always get the "Wrong Answer

Post by How-Yun Yin »

I think my code is correct
I have test my code with sample input
and i think the result is corredt,too!
but I always get the "Wrong Answer" from Online Judge
who can help me test my code and result?
input

Code: Select all

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

Code: Select all

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
[cpp]#include<iostream.h>
#include<string.h>
class block{
private:
int Index;
public:
block(){
}
block(int index){
setIndex(index);
}
int getIndex(){
return Index;
}
void setIndex(int index){
Index=index;
}
};
class stack{
private:
int mdata[25];
int sp;
public:
stack(){
sp=0;
}
void push(int data){
if(sp==25)return;
mdata[sp++]=data;
}
int pop(){
if(sp==0)return 0;
return mdata[--sp];
}
int getData(){
if(sp==0)return 0;
return mdata[sp-1];
}
int getSize(){
return sp;
}
void print(){
for(int i=0;i<sp;i++){
cout<<" "<<mdata;
}
}
};
class robot{
private:
block *bl;
stack *st;
int n;
public:
robot(int n,stack st[],block bl[]){
this->n=n;
this->bl=bl;
this->st=st;
}
void moveonto(int bsrc,int bdes){
int isrc,ides;
stack tmp1,tmp2;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp1.push((st+isrc)->pop());
}

while((st+ides)->getData()!=bdes){
tmp2.push((st+ides)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp1.getSize()!=0){
(st+isrc)->push(tmp1.pop());
}

while(tmp2.getSize()!=0){
(st+ides)->push(tmp2.pop());
}

}
void moveover(int bsrc,int bdes){
int isrc,ides;
stack tmp;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp.push((st+isrc)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp.getSize()!=0){
(st+isrc)->push(tmp.pop());
}
}
void pileonto(int bsrc,int bdes){
int isrc,ides;
stack tmp1,tmp2;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp1.push((st+isrc)->pop());
}
while((st+ides)->getData()!=bdes){
tmp2.push((st+ides)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp1.getSize()!=0){
(bl+tmp1.getData())->setIndex(ides);
(st+ides)->push(tmp1.pop());
}
while(tmp2.getSize()!=0){
(st+ides)->push(tmp2.pop());
}
}
void pileover(int bsrc,int bdes){
int isrc,ides;
stack tmp;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp.push((st+isrc)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp.getSize()!=0){
(bl+tmp.getData())->setIndex(ides);
(st+ides)->push(tmp.pop());
}
}
void print(){
for(int i=0;i<n;i++){
cout<<i<<":";
(st+i)->print();
cout<<endl;
}
}
};
int main(void){
char cmd1[5],cmd2[5];
int bsrc,bdes;
int n;
robot *r;
block *bl;
stack *st;
cin>>n;

if(n<1||n>24)return 1;
bl=new block[n];
st=new stack[n];
for(int i=0;i<n;i++){
(bl+i)->setIndex(i);
(st+i)->push(i);
}
r=new robot(n,st,bl);
while(1){
cin>>cmd1;
if(strcmp(cmd1,"quit")==0)break;
cin>>bsrc>>cmd2>>bdes;
if(bsrc==bdes)continue;
if(strcmp(cmd1,"move")==0){
if(strcmp(cmd2,"onto")==0){
r->moveonto(bsrc,bdes);
}
if(strcmp(cmd2,"over")==0){
r->moveover(bsrc,bdes);
}
}
if(strcmp(cmd1,"pile")==0){
if(strcmp(cmd2,"onto")==0){
r->pileonto(bsrc,bdes);
}
if(strcmp(cmd2,"over")==0){
r->pileover(bsrc,bdes);

}
}
}
r->print();

return 0;
}[/cpp]

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

Post by 1_UtterBlue »

You may have mistaken the words in the problems. See difference between moveonto and pileonto may be of help.
James.Hao (Bonjour!)

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

P101, an ever strange mistake!!! Help!!!

Post by 1_UtterBlue »

[pascal]
Program Blocks(input,output);
Type
pointer=^node;
node=record
num,cur_stack:integer;
prev,next:pointer;
end;

Var n:integer;
cmd:string;
queue:array[0..24] of node;
boxes:array[0..24] of node;

Procedure Display;
var i,j:integer;
p:pointer;
begin
for i:=0 to n-1 do
begin
write(i,':');
if boxes.next<>NIL then
begin
p:=boxes.next;
while p<>NIL do
begin write(' ',p^.num);p:=p^.next; end;
end;
writeln;
end;
end;

Procedure Initialize;
Var i:integer;
begin
for i:=0 to n-1 do
begin
queue.num:=i;
queue.next:=NIL;
queue.prev:=@boxes;
queue.cur_stack:=i;
boxes.next:=@queue;
end;
end;

Procedure moveonto(a,c:integer);
begin
(queue[a].prev^).next:=queue[a].next;
if queue[a].next<>NIL then
(queue[a].next^).prev:=queue[a].prev;
queue[a].cur_stack:=queue[c].cur_stack;
queue[a].next:=queue[c].next;
(queue[c].next^).prev:=@queue[a];
queue[c].next:=@queue[a];
queue[a].prev:=@queue[c];
end;

Procedure moveover(a,c:integer);
Var p:pointer;
begin
(queue[a].prev^).next:=queue[a].next;
if queue[a].next<>NIL then
(queue[a].next^).prev:=queue[a].prev;
queue[a].cur_stack:=queue[c].cur_stack;
p:=@queue[c];
While p^.next<>NIL do p:=p^.next;
queue[a].next:=NIL;
queue[a].prev:=p;p^.next:=@queue[a];
end;

Procedure pileover(a,c:integer);
Var p:pointer;
begin
queue[a].prev^.next:=NIL;
p:=@queue[a];
While p^.next<>NIL do
begin
queue[p^.num].cur_stack:=queue[c].cur_stack;
p:=p^.next;
end;
p^.cur_stack:=queue[c].cur_stack;
p:=@queue[c];
While p^.next<>NIL do p:=p^.next;
p^.next:=@queue[a];
queue[a].prev:=p;
end;

Procedure pileonto(a,c:integer);
Var p:pointer;
begin
queue[a].prev^.next:=NIL;
p:=@queue[a];
While p^.next<>NIL do
begin
queue[p^.num].cur_stack:=queue[c].cur_stack;
p:=p^.next;
end;
p^.cur_stack:=queue[c].cur_stack;
p^.next:=queue[c].next;
queue[c].next^.prev:=p;
queue[c].next:=@queue[a];
queue[a].prev:=@queue[c];
end;

Function legal(a,c:integer):boolean;
begin
legal:=true;
if (a=c) or (queue[a].cur_stack=queue[c].cur_stack) then
begin legal:=false;exit;end;
if (a<0) or (a>n-1) or (c<0) or (c>n-1) then legal:=false;
end;

Procedure Cmd_Parse;
Var command:string;
num1,num2,t,m:integer;
begin
command:=copy(cmd,1,4);
delete(cmd,1,5);
t:=1;
while cmd[t]<>' ' do t:=t+1;
Val(copy(cmd,1,t-1),num1,m);
delete(cmd,1,t);
command:=command+copy(cmd,1,4);
delete(cmd,1,5);
Val(cmd,num2,m);
If legal(num1,num2) then
begin
if command='moveonto' then moveonto(num1,num2)
else if command='moveover' then moveover(num1,num2)
else if command='pileonto' then pileonto(num1,num2)
else if command='pileover' then pileover(num1,num2);
end;
end;
begin
Readln(n);
Initialize;
Readln(cmd);
While cmd<>'quit' do
begin
Cmd_Parse;
Readln(cmd);
end;
Display;
end.

[/pascal]
I got the answer as
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference


What's wrong? I used fixed array to store all the boxes. (Array queue) and array BOX is used to store the link for each stack. Every stack is started with a head node.
Anyone's help is appreciated! Thanks. :o
James.Hao (Bonjour!)

Admiral
New poster
Posts: 1
Joined: Thu Aug 08, 2002 2:12 pm
Location: Shanghai China

problem 101, why do I get wrong answer?

Post by Admiral »

Array pre means the previous box of each box, if there's not a previous box then set as -1, the same as other arrays. Array first means the first box of each stack, and array position means the position of every box.
[c]#include <stdio.h>

void main(void)
{
short i,n,a,b,p;
short pre[25],next[25],first[25],position[25];
char comm1[5],comm2[5];

scanf("%d",&n);
for (i=0;i<n;i++)
{
position=first=i;
pre=next=-1;
}
scanf("%s",comm1);
while (comm1[0]!='q')
{
scanf("%d%s%d",&a,comm2,&b);
if (a!=b && position[a]!=position)
{
if (comm1[0]=='m')
{
if (comm2[1]=='n')
{
if (pre[a]!=-1) next[pre[a]]=next[a];
if (next[a]!=-1) pre[next[a]]=pre[a];
if (first[position[a]]==a) first[position[a]]=next[a];
pre[a]=b;
next[a]=next;
next=a;
if (next[a]!=-1) pre[next[a]]=a;
position[a]=position;
}//move onto
else
{
if (pre[a]!=-1) next[pre[a]]=next[a];
if (next[a]!=-1) pre[next[a]]=pre[a];
if (first[position[a]]==a) first[position[a]]=next[a];
p=b;
while (next[p]!=-1) p=next[p];
next[a]=-1;
next[p]=a;
pre[a]=p;
position[a]=position;
}//move over
}
else
{
if (comm2[1]=='n')
{
if (pre[a]!=-1) next[pre[a]]=-1;
if (first[position[a]]==a) first[position[a]]=-1;
p=a;
while (next[p]!=-1)
{
position[p]=position;
p=next[p];
}
position[p]=position;
next[p]=next;
if (next[p]!=-1) pre[next[p]]=p;
next=a;
pre[a]=b;
}//pile onto
else
{
if (pre[a]!=-1) next[pre[a]]=-1;
if (first[position[a]]==a) first[position[a]]=-1;
p=b;
while (next[p]!=-1) p=next[p];
next[p]=a;
pre[a]=p;
while (next[p]!=-1)
{
p=next[p];
position[p]=position;
}
}//pile over
}
}
scanf("%s",comm1);
}
for (i=0;i<n;i++)
{
printf("%d:",i);
p=first;
while (p!=-1)
{
printf(" %d",p);
p=next[p];
}
printf("\n");
}
}[/c]

How-Yun Yin
New poster
Posts: 3
Joined: Sun Aug 04, 2002 11:00 am

Post by How-Yun Yin »

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

pile 8 over 2
0: 1 2 3 4 5 8 9 0
2: 6 7
is that right?
who can tell me?

nayaya
New poster
Posts: 9
Joined: Sat Jun 08, 2002 1:57 pm

Post by nayaya »

I think your size of the two arrays should be much much bigger. I got the same reply on 202, and I got AC after I enlarged the array. Try!

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

I've changed, nothing changed but my Runtime Error times.

Post by 1_UtterBlue »

I've enlarged my array upto 100. And I've spent the annoying 30m typing different awful command to test my program, nothing wrong with that!!! What's wrong lying there? That annoying? There must be something big and huge? Wish I was Harry Potter. :-?
James.Hao (Bonjour!)

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

Post by 1_UtterBlue »

Yes, that's right.
James.Hao (Bonjour!)

zalileo
New poster
Posts: 2
Joined: Fri Aug 16, 2002 7:08 am

// No, it's not right!

Post by zalileo »

it should be that:

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

pile 8 over 2 
0: 0 1 2 3 4 8 9
5: 5 6 7
// .....................................................

How-Yun Yin
New poster
Posts: 3
Joined: Sun Aug 04, 2002 11:00 am

Post by How-Yun Yin »

finally....i get it.....
thank you very very much!!!!!!!!!

jamesng
New poster
Posts: 3
Joined: Sun Aug 18, 2002 5:33 pm
Location: Singapore
Contact:

I still cannot get it...

Post by jamesng »

Hi guys, sorry to trouble you.
I've tested my code with the above cases and got the stated results.
However, I still get 'Wrong Answer' from the judge :cry:
May I know is there any exception cases that I may not have taken care of?
Thank you very much.

James

jamesng
New poster
Posts: 3
Joined: Sun Aug 18, 2002 5:33 pm
Location: Singapore
Contact:

Yeah, I got my program accepted.

Post by jamesng »

Just found out the mistake I made. Forgot to ignore the commands for blocks in the same stack. :D

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:

Problem 101

Post by Spike »

Okay... what if the initial configuration is like this

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

and the command is "move 4 onto 5"

You're supposed to move all blocks on top of 4 and 5 to their original positions. However, 0 is in it's original position.

Do you move 0 under 5? You shouldn't ignore it because 4 and 5 are not in the same pile.

Please help me figure this one out.

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:

Post by Spike »

nevermind... I'm stupid.
you could never get into that position, because you couldn't get 5 there.

Therefore, you can correctly assume that the block on the bottom of a pile is always going to be the same block # as the pile number.

Post Reply

Return to “Volume 1 (100-199)”