101 - The Blocks Problem

[Eduard]

Thanks Ghust_omega you help me to find some of my mistakes.Now I'm getting right answer for your test too,but I'm still getting WA.
Please give me some more tests.
Thanks.

[Ghust_omega]

Hi Eduard here more I/O I genereted this I/O randomly
Input:

Code: Select all

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

ouput

Code: Select all

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

one more

Input

Code: Select all

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

ouput:

Code: Select all

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

I hope that this helps you
Keep posting!!!

[Eduard]

Thank you vary much Ghust_omega.
With your inputs I find my last mistak and got AC.
Thanks.

[eg_frx]

I thought 101 would be an easy challenge.

I've run my code with VC++ and Unix g++ for millions of times and both generate correct answer (as far as it seems to me). However, when I submitted it to the online judge, it kept complaining on a RUNTIME ERROR (SIGSEGV) - Invalid memory reference.

Since my trial runs give no erros, and the judge won't tell me how this mistake is produced, I've beaten my brain out, yet still don't see why.

Could anyone tell me what this Error message mean? and why does it happen? I'll be most grateful.

Below are my codes. To thoes who may ask why I use strange variable names like plc and tteemmp etc. , I thought I was using some of the key words, so I came up with these weird identifiers to make sure they didn't cause the trouble.

Code: Select all

#include <iostream>
#include <stack>

using namespace std;

void main(){
	int total;
	stack<int> blks[25];
	stack<int> pp;
	int plc[25];
	char commf[100], commb[100];
	int a, b;
	int tteemmp;
	
	cin >> total;

	for (int lv1 = 0; lv1 < total; lv1++){
		plc[lv1] = lv1;
		blks[lv1].push(lv1);
	}

	for(;;){
		cin >> commf;
	
		if (commf[0] == 'q')
			break;

		cin >> a >> commb >> b;

		if (commf[0] == 'm'){
			do{
				tteemmp = blks[plc[a]].top();
				blks[plc[a]].pop();
				if (tteemmp != a){
					blks[tteemmp].push(tteemmp);
					plc[tteemmp] = tteemmp;
				}
			} while (tteemmp != a);

			if (commb[1] == 'n'){
				for (tteemmp = blks[plc[b]].top(); tteemmp != b; tteemmp = blks[plc[b]].top()){
					blks[plc[b]].pop();
					blks[tteemmp].push(tteemmp);
					plc[tteemmp] = tteemmp;
				}
			}

			blks[plc[b]].push(a);
			plc[a] = plc[b];
		}

		else {

			if (commb[1] == 'n'){
				for (tteemmp = blks[plc[b]].top(); tteemmp != b; tteemmp = blks[plc[b]].top()){
					blks[plc[b]].pop();
					blks[tteemmp].push(tteemmp);
					plc[tteemmp] = tteemmp;
				}
			}

			do{
				pp.push(blks[plc[a]].top());
				blks[plc[a]].pop();
			} while (pp.top() != a);

			while (!pp.empty()){
				blks[plc[b]].push(pp.top());
				pp.pop();
				plc[blks[plc[b]].top()] = plc[b];
			}
		}
	}


	for (int lv2 = 0; lv2 < total; lv2++){
		cout << lv2 << ':';

		while (!blks[lv2].empty()){
			pp.push(blks[lv2].top());
			blks[lv2].pop();
		}

		while (!pp.empty()){
			cout << ' '<< pp.top();
			pp.pop();
		}

		cout << endl;
	}
}

[dumb dan]

> Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.

This input will result in runtime error for you:

10
move 6 onto 6
quit

[PerHagen]

hello, my code in pascal is:


--------------------------------------------------
program Acm101(input,output);
type
Arreglo=array[1..27,1..27]of integer;
str4=string[4];
str5=string[5];

procedure GeneraArreglo(var M:arreglo;n:integer);
VAR i:integer;
begin
for i:=1 to n do begin
M[i,1]:=i-1;
M[i,2]:=200;
end;
end;

function posY(M:arreglo;a:integer;n:integer):integer;
var i,j:integer;
encontrado:boolean;
begin
i:=1; encontrado:=false;
while not(encontrado) do begin
j:=1;
while not(encontrado)and (M[i,j]<>200) do begin
if M[i,j]=a then encontrado:=true;
j:=j+1;
end;
i:=i+1;
end;
posY:=j-1;
end;

function posX(M:arreglo;a:integer;n:integer):integer;
var i,j:integer;
encontrado:boolean;
begin
i:=1; encontrado:=false;
while not(encontrado) do begin
j:=1;
while not(encontrado)and (M[i,j]<>200) do begin
if M[i,j]=a then encontrado:=true;
j:=j+1;
end;
i:=i+1;
end;
posX:=i-1;
end;

procedure Coloca(var M:arreglo;a,b:integer);
var i1,j1,i,j,n:integer;
encontrado:boolean;
begin
i:=posX(M,b,n);
j:=posY(M,b,n);
encontrado:=false;
while not(encontrado) do begin
if M[i,j+1]=200 then
begin
i1:= posX(M,a,n);
j1:= posY(M,a,n);
M[i,j+1]:=M[i1,j1];
M[i,j+2]:=200;
M[i1,j1]:=200;
encontrado:=true;
end;
j:=j+1;
end;
end;

procedure ColocaPIla(var M:arreglo;a,b:integer);
var i,j,i2,j2,n:integer;
encontrado,finish:boolean;
begin
i:=posX(M,b,n);
j:=posY(M,b,n);
encontrado:=false;
while not(encontrado) do begin
if M[i,j+1]=200 then
begin
i2:=posX(M,a,n);
j2:=posY(M,a,n);finish:=false;
while not(finish) do begin
M[i,j+1]:=M[i2,j2];
M[i2,j2]:=200;
j:=j+1;
j2:=j2+1;
if M[i2,j2]=200 then
begin
finish:=true;
M[i,j+1]:=200;
end;
end;
encontrado:=true;
end;
j:=j+1;
end;
end;


procedure MovInto(var M:arreglo;a,b:integer;n:integer);
begin
if (M[posX(M,a,n),posY(M,a,n)+1]=200)and(posX(M,a,n)<>posX(M,b,n)) then
if (M[posX(M,b,n),posY(M,b,n)+1]=200) then Coloca(M,a,b);
end;


procedure MovOver(var M :arreglo; a,b:integer;n:integer);
begin
if (M[posX(M,a,n),posY(M,a,n)+1]=200)and(posX(M,a,n)<>posX(M,b,n)) then Coloca(M,a,b);
end;


procedure PilInto(var M:arreglo; a,b:integer;n:integer);
begin
if ((posX(M,a,n))<>posX(M,b,n))and(M[posX(M,b,n),posY(M,b,n)+1]=200) then ColocaPila(M,a,b);
end;


procedure PilOver(var M:arreglo; a,b:integer;n:integer);
begin
if (posX(M,a,n)<>posX(M,b,n)) then ColocaPIla(M,a,b);
end;

procedure MuestraMatrix(M:arreglo;n:integer);
var i,j:integer;
begin
i:=1;
while (i<=n) do begin
j:=1;
write((i-1), ':');
while (M[i,j]<>200) do begin
write(' ',(M[i,j]));
j:=j+1;
end;
i:=i+1;
if i<n then writeln;
end;
end;

var n,a,b :integer;
M :Arreglo;
TipMov:str4;
TipTras:str5;
finish:boolean;

begin
readln(n);
GeneraArreglo(M,n);
finish:=false;
while not(eof(input))and not(finish) do begin
read(tipMov);
if (tipMov<>'quit') then
begin
readln(a,TipTras,b);
if (TipMov='move')and((a<n) and (b<n)) then
begin
if TipTras=' onto' then MovInto(M,a,b,n);
if TipTras=' over' then MovOver(M,a,b,n);
end;
if (TipMov='pile')and((a<n)and(b<n)) then
begin
if TipTras=' onto' then PilInto(M,a,b,n);
if TipTras=' over' then PilOver(M,a,b,n);
end;
end;
if TipMov='quit' then finish:=true;
end;
MuestraMatrix(M,n);
end.

-------------------------------------
i don't understand ...is bad ,wrong answer
help me !!!![pascal][/pascal]

[Ghust_omega]

Hi !! PerHagen here I put some I/O i dont code in Pascal but try with that I/O to see whats it wrong
http://online-judge.uva.es/board/viewtopic.php?t=6452

Hope it Helps
Keep posting !!

[PerHagen]

thanks !!!!!
Eres de vnezuela ,entnces entiendes esto

Mus gracias mi cdigo corrio,yo ya perdia las ganas de seguir presetando soluciones pero me subio los animos
saludos de Peru

[Ghust_omega]

Hi !! PerHagen my hints helps you ?? you finally get AC or WA??, and dont give up about the submit there are things that we can detect so easy, so in that way this forum helps you but you have to know how to use, because depend of the forum is bad, so try to make some problems easy first in http://felix-halim.net/oj/problems.php put your Id and they give you the next 20 easy problems so... you can make some problems
Hope it Helps
Keep posting !!

[billwang]

My source file(CPP):
[cpp]code
include <stdio.h>
#define MaxB 100

typedef struct block {
int name;
struct block *below;
struct block *above;
} block;

block blocks[MaxB];
block *table[MaxB];
int NumBlocks;

void InitBlock()
{
for (int i=0;i<NumBlocks;i++){
blocks.name=i;
blocks.below=(block*) NULL;
blocks.above=(block*) NULL;
table=&blocks;
}
}

int IsOver(int n ,int k)
{
block *temp;

temp = table[k];
while (temp){
if (temp->name == n)
return 1;
temp = temp->above;
}
return 0;
}

block *BlockTop(int n)
{
block *temp=table[n];
while (temp->above!=(block*) NULL){
temp=temp->above;
}
return temp;
}

void ClearBlockAbove(int n)
{
block *top ,*next;
top=BlockTop(n);
while (top!=table[n]){
next=top->below;
top->above=(block*) NULL;
top->below=(block*) NULL;
top=next;
}
table[n]->above = (block *) NULL;
}


void MoveOnto(int a, int b)
{
ClearBlockAbove(a);
ClearBlockAbove(b);
table->above=table[a];
if (table[a]->below)
table[a]->below->above= (block*) NULL;
table[a]->below=table;
}

void MoveOver(int a , int b)
{
block *top;
ClearBlockAbove(a);
top=BlockTop(b);
top->above=table[a];
if (table[a]->below)
table[a]->below->above= (block*) NULL;
table[a]->below=top;
}

void PileOnto(int a ,int b)
{
ClearBlockAbove(b);
table->above=table[a];
if (table[a]->below)
table[a]->below->above= (block*) NULL;
table[a]->below=table;
}

void PileOver(int a ,int b)
{
block *top;
top->above=table[a];
if (table[a]->below)
table[a]->below->above= (block*) NULL;
table[a]->below=top;
}




int main()
{
char act1[10] ,act2[10] ;
int a , b ,i;
block *bottom;
scanf("%d",&NumBlocks);
InitBlock();
while (1){
scanf("%s",act1);
if (act1[0]=='q') break;
scanf("%d %s %d",&a,act2,&b);
if (a == b || IsOver(a,b) || IsOver(b,a)) continue;
if (act1[0]=='m')
if (act2[1]=='n') MoveOnto(a,b);
else MoveOver(a,b);
else
if (act2[1]=='n') PileOnto(a,b);
else PileOver(a,b);

}
for (i=0;i<NumBlocks;i++){
printf("%d:",i);
if (table->below!=(block*) NULL)
printf("\n");
else{
bottom=table;
while (bottom){
printf(" %d",bottom->name);
bottom=bottom->above;
}
printf("\n");
}
}
}[/cpp]

[eg_frx]

Maybe you didn't ignore the 'invalid' commands.

[Zuza]

SIGSEGV is a runtime error that happens when you reference memory out of bounds. It can happen when you (let's say) allocate an array of 100 members and then you start to write on position array[150] or so.

[Blueteeth]

I have this error too !! wanna know why ?! if possible
[cpp]#include <iostream>
#include <stack>
#include <string>
using namespace std;

inline int to_dig (char c) { return c-48; }
inline char to_char (int n) { return char(n+48); }
inline void tokenize (string& comm , string par[4])
{
string temp="";
int j=0;
for (int i=0 ; i<comm.size() ; i++)
{
if ( comm == ' ' )
{
par[j++] = temp;
temp = "";
}
else
temp += comm;
}
par[j] = temp;
}

void Move (stack<int> w[] , int pos[] , int n , int a , int b , string& mode)
{
int a_stack_num = pos[a];
int b_stack_num = pos;
int A,B;
while ( (A=w[ a_stack_num ].top()) != a ) // return all to their initial positions
{
w[ a_stack_num ].pop();
w[A].push(A); // put back
pos[A] = A;
}

if ( mode == "onto" ) //remove all above b
{
while ( (B=w[ b_stack_num ].top()) != b )
{
w[ b_stack_num ].pop();
w.push(B);
pos = B;
}
}

w[ a_stack_num ].pop();
w[ b_stack_num ].push(a);
pos[a] = b_stack_num;
}

void Pile (stack<int> w[] , int pos[] , int n , int a , int b , string& mode)
{
int a_stack_num = pos[a];
int b_stack_num = pos;
stack<int> a_stack;

int A,B;
while ( true )
{
A = w[ a_stack_num ].top();
a_stack.push(A);
w[ a_stack_num ].pop();
if ( A == a ) break;
}

if ( mode == "onto" ) //remove all above b
{
while ( (B=w[ b_stack_num ].top()) != b )
{
w[ b_stack_num ].pop();
w.push(B);
pos = B;
}
}

while ( !(a_stack.empty()) )
{
int cur = a_stack.top();
a_stack.pop();
w[ b_stack_num ].push(cur);
pos[cur] = b_stack_num;
}
}






inline void act (stack<int> w[] , int pos[] , int n , string comm[4])
{
if ( comm[0] == "move" )
Move(w,pos,n,to_dig(comm[1][0]),to_dig(comm[3][0]),comm[2]);
else
Pile(w,pos,n,to_dig(comm[1][0]),to_dig(comm[3][0]),comm[2]);

}

void disp ( stack<int> w[] , int n )
{
int* buff = new int[n];
int sz=0;
for (int i=0 ; i<n ; i++)
{
cout << i << ":";
while ( !(w.empty()) )
{
buff[sz++] = w.top();
w.pop();
}
for (int j=sz-1 ; j>=0 ; j--)
cout << ' ' << buff[j];
sz=0;
cout << endl;
}
delete[] buff;
}



int main()
{
//ifstream in("in.txt");
int num_blocks;
cin >> num_blocks;
stack<int>* world = new stack<int>[num_blocks];
int* positions = new int[num_blocks];
for (int i=0 ; i<num_blocks ; i++)
{
world.push(i);
positions = i; // initial position for each block
}

string command;
string parsed_com[4];
cin.ignore();
getline(cin,command);
while ( command != "quit" )
{
tokenize(command,parsed_com);
act(world,positions,num_blocks,parsed_com);
getline(cin,command);
}


disp(world,num_blocks);

delete[] world;
delete[] positions;
cin.get();
return 0;
}
[/cpp]

[frankhuhu]

I don't know why my code will have Runtime Error.I have thought it for many times,but I can not work it out.Is there anyone who can help me?Thanks a lot!!!

Here is my code:

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

int table[25][25];

struct Stack
{
int x,y;
}block[25];

void move_onto(int a,int b);
void move_over(int a,int b);
void pile_onto(int a,int b);
void pile_over(int a,int b);

int main()
{
int N,a,b;
char cmd1[10],cmd2[10];
int i,j;

cin>>N;
//initilize block
for (i=0;i<25;i++)
for (j=0;j<25;j++)
table[j]=-1;
for (j=0;j<N;j++)
table[j][0]=j;
for (i=0;i<N;i++)
{
block.x=i;
block.y=0;
}
//end initilization
while (cin>>cmd1>>a>>cmd2>>b)
{
if (strcmp(cmd1,"quit")==0) break;
if (a==b) continue;
if (strcmp(cmd1,"move")==0 && strcmp(cmd2,"onto")==0) move_onto(a,b);
if (strcmp(cmd1,"move")==0 && strcmp(cmd2,"over")==0) move_over(a,b);
if (strcmp(cmd1,"pile")==0 && strcmp(cmd2,"onto")==0) pile_onto(a,b);
if (strcmp(cmd1,"pile")==0 && strcmp(cmd2,"over")==0) pile_over(a,b);
}
//print result;
for(i=0;i<N;i++)
{
cout<<i<<":";
for(j=0;j<N;j++)
{
if(table[j]!=-1)
{
cout<<" "<<table[j];
}
}
cout<<'\n';
}


return 0;
}

void move_onto(int a,int b)
{
int a_x,a_y,b_x,b_y;
a_x=block[a].x;
a_y=block[a].y;
b_x=block.x;
b_y=block.y;
while (table[a_x][a_y+1]!=-1)
{
block[table[a_x][a_y+1]].x=table[a_x][a_y+1];
block[table[a_x][a_y+1]].y=0;
table[table[a_x][a_y+1]][0]=table[a_x][a_y+1];
table[a_x][a_y+1]=-1;
a_y++;
}
while (table[b_x][b_y+1]!=-1)
{
block[table[b_x][b_y+1]].x=table[b_x][b_y+1];
block[table[b_x][b_y+1]].y=0;
table[table[b_x][b_y+1]][0]=table[b_x][b_y+1];
table[b_x][b_y+1]=-1;
b_y++;
}
table[block.x][block.y+1]=a;
table[block[a].x][block[a].y]=-1;
block[a].x=block.x;
block[a].y=block.y+1;
}

void move_over(int a,int b)
{
int a_x,a_y,b_x,b_y,top;
a_x=block[a].x;
a_y=block[a].y;
while (table[a_x][a_y+1]!=-1)
{
block[table[a_x][a_y+1]].x=table[a_x][a_y+1];
block[table[a_x][a_y+1]].y=0;
table[table[a_x][a_y+1]][0]=table[a_x][a_y+1];
table[a_x][a_y+1]=-1;
a_y++;
}
b_x=block.x;
top=b_y=block.y;
while (table[b_x][top]!=-1)
top++;
table[block.x][top]=a;
table[block[a].x][block[a].y]=-1;
block[a].x=block.x;
block[a].y=top;
}

void pile_onto(int a,int b)
{
int a_x,a_y,b_x,b_y,top;
b_x=block[b].x;
b_y=block[b].y;
while (table[b_x][b_y+1]!=-1)
{
block[table[b_x][b_y+1]].x=table[b_x][b_y+1];
block[table[b_x][b_y+1]].y=0;
table[table[b_x][b_y+1]][0]=table[b_x][b_y+1];
table[b_x][b_y+1]=-1;
b_y++;
}
top=block[b].y+1;
a_x=block[a].x;
a_y=block[a].y;
while (table[a_x][a_y]!=-1)
{
table[block[b].x][top]=table[a_x][a_y];
block[table[a_x][a_y]].x=block[b].x;
block[table[a_x][a_y]].y=top;
table[a_x][a_y]=-1;
top++;a_y++;
}
}

void pile_over(int a,int b)
{
int a_top,b_top;
int a_x,a_y,b_x,b_y;
a_x=block[a].x;
a_top=a_y=block[a].y;
b_x=block[b].x;
b_top=b_y=block[b].y;
if (a_x==b_x) return;
while (table[b_x][b_top]!=-1)
b_top++;
while (table[a_x][a_y]!=-1)
{
table[block[b].x][b_top]=table[a_x][a_y];
block[table[a_x][a_y]].x=block[b].x;
block[table[a_x][a_y]].y=b_top;
table[a_x][a_y]=-1;
b_top++;a_y++;
}
}

[Evan Tsang]

Check your pile_onto() function.

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

-evan