Page 18 of 43

Posted: Tue Jan 27, 2004 3:23 pm
by zolto
Thanks for all the help, it works now. There were some minor (stupid) errors.

Posted: Tue Jan 27, 2004 5:45 pm
by junbin
Not really helpful.. but here's a tip:

Most people on this forum solved volume 1 questions quite some time ago and most don't remember the specifics...

The best way to get a response is to make a sample test data with all the data you think MAY trip your program. Post the test data and your test output and hopefully someone will post their output and if there is any discrepancies, you can use that to debug...

I hate to say it, but most people just can't find the time to re-solve a question just to help someone else debug their program... it's cruel, but it's human nature. :(


Anyway, try these:

Moving a empty stack
Moving onto an empty stack
etc.

Usually TLE/WA for this kind of simple simulation questions is due to boundary errors.

Posted: Tue Jan 27, 2004 6:49 pm
by scruff
You can also use the search feature and just type in "101" there a quite a few topics already and test data that has tripped up others. Also http://people.eecs.ku.edu/~rucker/valladolid/p101.exe heres a test generator and answer program. It will give an input and give the solution to that input. Just run the input through your program to see if you get the same output. If not then debug.

Happy Coding.

Problem 101 - Runtime error (SIGSEGV)

Posted: Sat Feb 14, 2004 5:45 pm
by aditya
[cpp]

#include <string>
#include <iostream>
using namespace std;

const int MAXNUM = 25;

enum Boolean { FALSE, TRUE };
void Reset( int *block[], int row_a, int a );
void Move( int *block[], int row_a, int a, int b );
int Find( int *block[], int a, int n );
void Initialise( int *block[], int n ) ;
void Display( int *block[], int n );
void Pile( int *block[], int row_a, int a, int row_b );

int main() {
string action, prep;
int *block[MAXNUM];
int n;
int i;
int a, b;
int row_a, row_b;

cin >> n;
for( i = 0; i < n; i++ )
block = (int *) malloc( 25 * sizeof(int) );

Initialise( block, n );
while( TRUE ) {
cin >> action;
if( action == "quit" ) break;
cin >> a >> prep >> b;
if( a == b ) continue;

row_a = Find( block, a, n );
/* find the row where block a is in */
row_b = Find( block, b, n );
if( row_a == row_b )
continue;
if( action == "move" ) {
if( prep == "onto" ) {
Reset( block, row_a, a );
Reset( block, row_b, b );
Move( block, row_a, a, row_b );
}
else if( prep == "over" ) {
Reset( block, row_a, a );
Move( block, row_a, a, row_b );
}
}
else if( action == "pile" ) {
if( prep == "onto" ) {
Reset( block, row_b, b );
Pile( block, row_a, a, row_b );
}
else if( prep == "over" )
Pile( block, row_a, a, row_b );
}

}

Display( block, n );
return 1;

}

int Find( int *block[], int a, int n ) {
int i, j;

for( i = 0; i < n; i++ )
for( j = 0; j < MAXNUM; j++ )
if( block[j] == a )
return i;
return( FALSE );
}

void Reset( int *block[], int row_a, int a ) {
int i, temp;

for( i = 0; block[row_a] != a; i++ )
;

i++;
for( ; block[row_a] != -1; i++ ) {
temp = block[row_a];
block[temp][0] = temp;
block[row_a] = -1;
}

}

void Move( int *block[], int row_a, int a, int row_b) {

int i;

for( i = 0; block[row_a] != a; i++ )
;

block[row_a] = -1;

for( i = 0; block[row_b] != -1; i++ )
;

block[row_b] = a;
i++;
block[row_b][i] = -1;
}

void Initialise( int *block[], int n ) {
int i, j;

for( i = 0; i < n; i++ ) {
block[i][0] = i;
block[i][1] = -1;
for( j = 2; j < MAXNUM; j++ )
block[i][j] = 0;
}
}

void Display( int *block[], int n ) {
int i, j;

for( i = 0; i < n; i++ ) {
cout << i << ":";
for( j = 0; block[i][j] != -1; j++ )
cout << " " << block[i][j] ;
cout << endl;
}

void Pile( int *block[], int row_a, int a, int row_b ) {
int i;

for( i = 0; block[row_a][i] != a; i++ )
;
for( ; block[row_a][i] != -1; i++ ) {
Move( block, row_a, block[row_a][i], row_b );
block[row_a][i] = -1;
}

}
[/cpp]

my code is running just fine for the sample input....without any sort of runtime errors....
can anybody plssss.....tell me what the problem could be......
i
thanx.

101 Compile Error.

Posted: Sat Feb 21, 2004 6:16 am
by JW
I use gcc 3.2.2, and compiled it successfully.
[cpp]#include <iostream>
#include <vector>


using namespace std;

class Blocks
{
typedef vector<short> cvectype;
vector<cvectype> vec;
class block_pos
{
public:
short row;
short column;
block_pos(short r, short c):row(r), column(c){}
};

block_pos block_find(short block_value)
{
register short row, column;
for (row = 0; row < vec.size(); row++)
for (column = 0; column < vec[row].size(); column++)
if (vec[row][column] == block_value) return block_pos(row, column);
}

void block_delete(block_pos block)
{
vector<short>::iterator iter = vec[block.row].begin();
advance(iter, block.column);
vec[block.row].erase(iter);
}

void pile_delete(block_pos begin_b)
{
vector<short>::iterator iter = vec[begin_b.row].begin();
advance(iter, begin_b.column);
vec[begin_b.row].erase(iter, vec[begin_b.row].end());
}

void block_return(block_pos block)
{
short value = vec[block.row][block.column];
block_delete(block);
vec[value].push_back(value);
}

void pile_return(block_pos begin_b)
{
register short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
block_return(block_pos(begin_b.row, i));
pile_delete(begin_b);
}

short blocks_at_same_row(block_pos a, block_pos b)
{
if (a.row == b.row) return 1;
else return 0;
}

short block_can_return(block_pos block)
{
if (vec[vec[block.row][block.column]].empty()) return 1;
else return 0;
}

short pile_can_return(block_pos begin_b)
{
register short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
if (!block_can_return(block_pos(begin_b.row, i))) return 0;
return 1;
}

void move_a_onto_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

// return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}

if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void move_a_over_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
//return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void pile_a_onto_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

//return.
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

//pile.
register short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

void pile_a_over_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;

//pile.
register short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

public:
Blocks(short n)
{
register short i;
vector<short> cvec;
for (i = 0; i < n; i++)
{
cvec.push_back(i);
vec.push_back(cvec);
cvec.clear();
}
}

void print()
{
register short index, index1;
for (index = 0; index < vec.size(); index++)
{
cout << ' ' << index << " : ";
for (index1 = 0; index1 < vec[index].size(); index1++)
cout << vec[index][index1] << ' ';

cout << "\n";
}
}

void command(string action, short a, string grep, short b)
{
if (action == "move")
{
if (grep == "onto") move_a_onto_b(a, b);
else if (grep == "over") move_a_over_b(a, b);
}
else if (action == "pile")
{
if (grep == "onto") pile_a_onto_b(a, b);
else if (grep == "over") pile_a_over_b(a, b);
}
}
};

int main(){
short n, a, b;
string action, grep;
cin >> n;
Blocks block = Blocks(n);
cin >> action;
while (action != "quit")
{
cin >> a >> grep >> b;
block.command(action, a, grep, b);
cin >> action;
}

block.print();
return 0;
}[/cpp]

Posted: Sat Feb 21, 2004 8:32 am
by aditya
Hi JW,

Try compiling with
gcc -Wall -pedantic and remove all the warnings.....
I had a similar problem earlier. My code was compiling but with some warnings and the online judge was giving me a compiler error.....if you want it will send you the detailed compiler error message on your email id.......that should help...and dont forget to get rid of ALL the warnings

Even i am working on problem 101 but getting a runtime error (SIGSEGV} with Illegal Memory Reference.
Could you please send me some tricky test inputs??

My code is as below :

[cpp]

#include <string>
#include <cstdlib>

#include <fstream>
using std::ifstream;

#include <iostream>
using namespace std;

const int MAXNUM = 25;
enum Boolean { FALSE, TRUE };

void Reset( int row_a, int a );
void Move( int row_a, int a, int row_b );
int Find( int a );
void Initialise( ) ;
void Display();
void Pile( int row_a, int a, int row_b );

int top[MAXNUM];
int n;
int *block[MAXNUM];

int main() {
string action, prep;
int i;
int a, b;
int row_a, row_b;
ifstream infile( "input.txt", ios::in );

if( !infile ) {
cerr << "File not found\n";
exit( 1 );
}

infile >> n;
if( n >= MAXNUM || ( n <= 0 ) ) exit(1);
for( i = 0; i < n; i++ )
block = new int[n];
Initialise();
while( TRUE ) {
infile >> action;
if( action == "quit" ) break;
infile >> a >> prep >> b;

if( (a >= n) || (b >= n) || ( a == b) || (a < 0) || (b < 0) )
continue;
row_a = Find( a );
row_b = Find( b ); /* find the rows in which a and b are present */
if( row_a == row_b ) continue;
if( action == "move" ) {
if( prep == "onto" ) {
Reset( row_a, a );
Reset( row_b, b );
Move( row_a, a, row_b );
}
else if( prep == "over" ) {
Reset(row_a, a );
Move(row_a, a, row_b );
}
}
else if( action == "pile" ) {
if( prep == "onto" ) {
Reset(row_b, b );

Pile( row_a, a, row_b );
}
else if( prep == "over" )
Pile( row_a, a, row_b );
}

}

Display( );
return 0;

}

int Find( int a ) {
int i, j;

for( i = 0; i < n; i++ )
for( j = 0; j <= top; j++ )
if( block[j] == a )
return i;
return( FALSE );
}

void Reset( int row_a, int a ) {
int i, temp, itop;

for( i = 0; ( block[row_a] != a) && (i < n); i++ )
;
itop = i;
i++;
for( ; i <= top[row_a]; i++ ) {
temp = block[row_a];
block[ block[row_a] ][0] = block[row_a];
top[temp]++;
}
top[row_a] = itop;

}

void Move( int row_a, int a, int row_b) {

int i;

for( i = 0; (block[row_a] != a) && (i < n); i++ )
;
if( i == n ) cout << "Illegal Memory Address";
i--;
top[row_a] = i;
for( i = 0; i <= top[row_b]; i++ )
;
block[row_b] = a;
top[row_b]++;
}

void Initialise( ) {
int i;

for( i = 0; i < n; i++ ) {
top = 0;
block[i][0] = i;
}
}

void Display( ) {
int i, j;

for( i = 0; i < n; i++ ) {
cout << i << ":";
for( j = 0; j <= top[i]; j++ )
cout << " " << block[i][j] ;
cout << endl;
}

for( i = 0; i < n; i++ )
delete [] block[i];
}

void Pile(int row_a, int a, int row_b ) {
int i, itop;
int j;

itop = top[row_a];
for( i = 0; (block[row_a][i] != a) && (i < n); i++ )
;
for( ; i <= itop; i++, j++ )
Move( row_a, block[row_a][i], row_b );

top[row_a] = i - j - 1;
}







[/cpp]

Posted: Sun Feb 22, 2004 3:51 am
by JW
Thank aditya. I used "-Wall" keyword to compile my program, I found some warnings, and I have already fixed it. However, it still got a "compile error".

I saw your code use file to input. Don't use file, just use keyboard to input, and output the result to screen.

Posted: Sun Feb 22, 2004 3:53 am
by JW
My new code is below.
[cpp]#include <iostream>
#include <vector>

using namespace std;

class Blocks
{
typedef vector<unsigned short> cvectype;
vector<cvectype> vec;
class block_pos
{
public:
unsigned short row;
unsigned short column;
block_pos(unsigned short r, unsigned short c):row(r), column(c){}
};

block_pos block_find(unsigned short block_value)
{
register unsigned short row, column;
for (row = 0; row < vec.size(); row++)
for (column = 0; column < vec[row].size(); column++)
if (vec[row][column] == block_value) return block_pos(row, column);

// can't find.
return block_pos(26, 26);
}

void block_delete(block_pos block)
{
vector<unsigned short>::iterator iter = vec[block.row].begin();
advance(iter, block.column);
vec[block.row].erase(iter);
}

void pile_delete(block_pos begin_b)
{
vector<unsigned short>::iterator iter = vec[begin_b.row].begin();
advance(iter, begin_b.column);
vec[begin_b.row].erase(iter, vec[begin_b.row].end());
}

void block_return(block_pos block)
{
unsigned short value = vec[block.row][block.column];
block_delete(block);
vec[value].push_back(value);
}

void pile_return(block_pos begin_b)
{
register unsigned short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
block_return(block_pos(begin_b.row, i));
pile_delete(begin_b);
}

unsigned short blocks_at_same_row(block_pos a, block_pos b)
{
if (a.row == b.row) return 1;
else return 0;
}

unsigned short block_can_return(block_pos block)
{
if (vec[vec[block.row][block.column]].empty()) return 1;
else return 0;
}

unsigned short pile_can_return(block_pos begin_b)
{
register unsigned short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
if (!block_can_return(block_pos(begin_b.row, i))) return 0;
return 1;
}

void move_a_onto_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

// return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}

if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void move_a_over_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
//return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void pile_a_onto_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

//return.
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

//pile.
register unsigned short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

void pile_a_over_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;

//pile.
register unsigned short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

public:
Blocks(unsigned short n)
{
register unsigned short i;
vector<unsigned short> cvec;
for (i = 0; i < n; i++)
{
cvec.push_back(i);
vec.push_back(cvec);
cvec.clear();
}
}

void print()
{
register unsigned short index, index1;
for (index = 0; index < vec.size(); index++)
{
cout << ' ' << index << " : ";
for (index1 = 0; index1 < vec[index].size(); index1++)
cout << vec[index][index1] << ' ';

cout << "\n";
}
}

void command(string action, unsigned short a, string grep, unsigned short b)
{
if (action == "move")
{
if (grep == "onto") move_a_onto_b(a, b);
else if (grep == "over") move_a_over_b(a, b);
}
else if (action == "pile")
{
if (grep == "onto") pile_a_onto_b(a, b);
else if (grep == "over") pile_a_over_b(a, b);
}
}
};

int main(){
unsigned short n, a, b;
string action, grep;
cin >> n;
Blocks block = Blocks(n);
cin >> action;
while (action != "quit")
{
cin >> a >> grep >> b;
block.command(action, a, grep, b);
cin >> action;
}

block.print();
return 0;
}
[/cpp]

Posted: Wed Feb 25, 2004 1:40 pm
by Krzysztof Duleba
Add #include <string>.

^^

Posted: Sat Feb 28, 2004 6:03 am
by Chung Ha, Yun
gits wrote:my code gives:

Code: Select all

0: 0
1: 1 2
2:
3:
4:
5: 5 4 6
6:
7: 7 9 3
8: 8
9:
10: 10 11 12
11:
12:
13: 13
14: 14 17
15: 15
16: 16
17:
18: 18
my question is, how do 7 9 3 go over 8 in the end?
Insert this condition. You will get accept.
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

101 - i am going crazy

Posted: Thu Mar 11, 2004 3:31 pm
by komunist
my code. It`s WA. I now why. BuTT :evil:
when i debug my code on test

4
move 1 onto 0
move 0 onto 1
move 0 onto 2
move 2 onto 1
quit

he otput
0: 0
1: 1 2
2:
3: 3

but when i run my program (klik on .exe file) and input then same test he otput

0: 0 2
1: 1
2:
3: 3
:o :o :o :-?

WHY ???????????????
var i,j,k,n,m:longint;

a1,b1:longint;
a,b:array [-1..25] of longint;
s:string;

procedure erase(k:longint);
begin
if (k=a[k]) or (a[k]=-1) then else erase(a[k]);
a[k]:=k;
end;

function prov(a1,b1:longint):longint;
var i,j,k:longint;
begin
i:=1;
if a1=b1 then i:=0 else
if a[a1]<>a1 then
begin
while a[a1]>-1 do
begin
if a[a1]=b1 then i:=0;
a1:=a[a1];
end;
end;
prov:=i;
end;

begin
readln(n);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to n do a[i-1]:=i-1;
while true do
begin
readln(s);
if pos('quit',s)>0 then break;
if pos('move',s)>0 then
begin
delete(s,1,5);val(copy(s,1,pos(' ',s)-1),a1,i);delete(s,1,pos(' ',s));
if pos('onto',s)>0 then
begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(a1);erase(b1);
for i:=0 to n-1 do if a=a1 then a:=-1;
a[a1]:=-1;a[b1]:=a1;
end else begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(a1); a[a1]:=-1;
for i:=0 to n-1 do if a=a1 then a:=-1;
k:=b1;
while (a[k]>=0) and (a[k]<>k) do k:=a[k];
a[k]:=a1;
end;
end else begin
delete(s,1,5);val(copy(s,1,pos(' ',s)-1),a1,i);delete(s,1,pos(' ',s));
if pos('onto',s)>0 then
begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(b1);
for i:=0 to n-1 do if a=a1 then a:=-1;
a[b1]:=a1;
end else begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
k:=b1;
for i:=0 to n-1 do if a=a1 then a:=-1;
while (a[k]>=0) and (a[k]<>k) do k:=a[k];
a[k]:=a1;
end;
end;
end;
fillchar(b,sizeof(b),0);
for i:=0 to n-1 do
begin
write(i:2,':');
if (b<>0) or (a=-1) then begin writeln;continue; end;
b[i]:=1;
j:=i;
while j<>-1 do
begin
write(' ',j);
b[j]:=1;
if j=a[j] then break;
j:=a[j];
end;
writeln;
end;
end.

Posted: Fri Mar 12, 2004 10:18 am
by komunist
Why program gives 2 diferent reply for 1 test

Time Limit Exceeded

Posted: Sat Apr 17, 2004 4:28 am
by cthompson
My submission for 101 is coming back time limit exceeded.

The time being usually 10.012 to 10.070 seconds, the limit is 10.000 seconds.

I was trying to shave that hundredth of a second, however it has occured to me that perhaps the online judge automatically stops a program that has been running longer then 10seconds.

ie my program could be exceeding the limit by far more then 10seconds if it were let run.

Is this the case?

Thanks,
Cassie

Posted: Sat Apr 17, 2004 5:36 am
by UFP2161
Yes, the judge will stop your program from running if it has run longer than 10 seconds.

Posted: Sat Apr 17, 2004 6:09 am
by cthompson
Thanks.