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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by 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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

Thank you vary much Ghust_omega.
With your inputs I find my last mistak and got AC. :)
Thanks. :wink:
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

101 - I'm driven crazy.

Post by 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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by 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
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

101 help me

Post by 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]
hello !

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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 !! :D

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

hi

Post by 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
hello !

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by 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 !! :D

billwang
New poster
Posts: 1
Joined: Tue Oct 19, 2004 2:51 pm

101 What is Runtime Error (SIGSEGV )

Post by 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
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx »

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

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

SIGSEGV

Post by 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
New poster
Posts: 4
Joined: Tue Nov 09, 2004 10:28 pm

Post by Blueteeth »

I have this error too !! wanna know why ?! if possible :roll:
[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
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Need Help on 101 ! Runtime Error (SIGSEGV )

Post by 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
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by 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

Post Reply

Return to “Volume 1 (100-199)”