101 - The Blocks Problem

[mamun]

if(a1.host==b1.host) return ;

Is this statement wrong ??

No.

What's your problem now? Invalid memory reference or something else?

[smilitude]

Dear Fahim:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.002 seconds.

--

PS: Check the board at http://acm.uva.es/board/

The Online Judge (Linux acm.uva.es 2.4.18-27.7.x i686)
Judge software version 2.8 [http://acm.uva.es/problemset/]
Fri Apr 21 07:17:44 UTC 2006

[Kyuubi]

I get the same memory error. I'm nearly at my wits end, because I've gone over my code multiple times, and I can't find anything wrong with it.

if anyone could tell me what is wrong with this I'd really appreciate it.

Code: Select all

removed

[edit]
I Managed to fix my error, it seems that a variable I was using as an array index wasn't initialized properly.

[Dai Ming]

Please look the program source blow.
it can give ringt answer on my computer
but when submit to UVA online-judge it gives wrong answer.
why?
I'm so puzzled.



#include <iostream>
#include <stdio.h>

using namespace std;

struct block
{
short no;
short fore;
short last;
short place;
};
short num;
block blocks[26];
//short n;
short x,y;
char a[6];
char w[6];

//the number of blocks.


void moveOnto()
{
short l;
short v;

for(l= blocks[x].last; l != -1;)
{
short temp = blocks[l].last;
blocks[l].place = blocks[l].no;
blocks[l].fore = -1;
blocks[l].last = -1;
l = temp;
}

blocks[x].last = -1;



for(v= blocks[y].last; v != -1;)
{
short temp1 = blocks[v].last;
blocks[v].place = blocks[v].no;
blocks[v].fore = -1;
blocks[v].last = -1;
v = temp1;
}


blocks[blocks[x].fore].last = -1;
blocks[x].fore = y;
blocks[y].last = x;
blocks[x].place = blocks[y].place;
}


void moveOver()
{
short top;
short l;

for(l= blocks[x].last; l != -1;)
{
short temp = blocks[l].last;
blocks[l].place = blocks[l].no;
blocks[l].fore = -1;
blocks[l].last = -1;
l = temp;
}

blocks[x].last = -1;

for(top = y;blocks[top].last != -1;top = blocks[top].last);

blocks[blocks[x].fore].last = -1;
blocks[top].last = x;
blocks[x].fore = top;
blocks[x].place = blocks[top].place;
}


void pileOnto()
{
short l;

for(l= blocks[y].last; l != -1;)
{
short temp = blocks[l].last;
blocks[l].place = blocks[l].no;
blocks[l].fore = -1;
blocks[l].last = -1;
l = temp;
}

blocks[blocks[x].fore].last = -1;
blocks[y].last = x;
blocks[x].fore = y;

for(l = x ; blocks[l].last != -1;)
{
blocks[l].place = blocks[y].place;
l = blocks[l].last;
}
blocks[l].place = blocks[y].place;
}


void pileOver()
{
short top;
short l;
for(top = y;blocks[top].last != -1;top = blocks[top].last);

blocks[blocks[x].fore].last = -1;
blocks[top].last = x;
blocks[x].fore = top;

for(l = x ; blocks[l].last != -1;)
{
blocks[l].place = blocks[y].place;
l = blocks[l].last;
}
blocks[l].place = blocks[y].place;
}


int main()
{
cin>>num;
//n = num;

for(int k = 0; k < num; k ++) //initial the table;
{
blocks[k].fore = -1;
blocks[k].no = k;
blocks[k].place = k;
blocks[k].last = -1;
}
blocks[num].no = -1;

while(1)
{
scanf("%s",a);
if(a[0] == 'q')
break;
else
{
scanf("%d%s%d",&x,w,&y);


if(x != y && blocks[x].place != blocks[y].place)
{
if (a[0] == 'm' && w[3] == 'r' )
moveOver();
if (a[0] == 'm' && w[3] == 'o')
moveOnto();
if (a[0] == 'p' && w[3] == 'r')
pileOver();
if (a[0] == 'p' && w[3] == 'o')
pileOnto();
}
}
}
//cout<<num<<endl;
for( short m = 0; blocks[m].no != -1; m ++)
{
if(blocks[m].no != blocks[m].place)
{
cout<<m<<":"<<endl;
} else
{
cout<<m<<":";
short th = m;
while(blocks[th].last != -1)
{
cout<<" "<<th;

th = blocks[th].last;



}
cout<<" "<<th<<endl;

}


return 0;
}

[jjtse]

another problem with java.

I've wrote java codes that run on windows and wouldn't run correctly on linux. Then I did some changes for it to work on linux, but now it wouldn't work on windows. The basic discrepancy between the two lies IO.

If we choose to read a line of input by reading one character at a time until the end of line, then we have issues. In linux, end of line is represented by one character: '\n' . In windows, end of line is represented by two character: '\n\r' .

When we submit programs, do we submit the version that works in linux, or the version that works in windows?


Here's my experience so far. when i submitted the version that works for windows, I get WA. When I submitted the version for linux, I get TLE. I'm guessing I should submit the linux version from now on. Can someone reaffirm this?


Thanks

[Darko]

I responded in that other thread in which you posted the same thing. I don't think either of them were appropriate, there is a Java forum on this board.

[Dai Ming]

I have got AC

[serur]

Fellows Hi!


I couldn't find out my bug, so I need your help.

I used double-end-queues. But it seems was no good

Thank you

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define N 25

typedef struct NODE{
	struct NODE *Next;
	struct NODE *Prev;
	short id;
}NODE;

InsertAfter(NODE *ExistingItem,NODE *NewItem)
{
	NewItem->Prev=ExistingItem;
	NewItem->Next=ExistingItem->Next;
	ExistingItem->Next=NewItem;
	if(NewItem->Next!=NULL)
		NewItem->Next->Prev=NewItem;
}
AddAfter(NODE **Item,short id)
{
	NODE *p=malloc(sizeof *p);
	p->Next=p->Prev=NULL;
	p->id=id;
	if(*Item==NULL)
		*Item=p;
	else
		InsertAfter(*Item,p);
}
typedef struct{
	NODE *HeadPtr;
	NODE *TailPtr;
	short NumItems;
}DEQUE;
Push(DEQUE *D,short id)
{
	AddAfter(&D->TailPtr,id);
	if(!D->NumItems)
		D->HeadPtr=D->TailPtr;
	else
		D->TailPtr=D->TailPtr->Next;
	++D->NumItems;
}
Pop(DEQUE *D,short *id)
{
	NODE *tmp=D->TailPtr->Prev;
	*id=D->TailPtr->id;
	free(D->TailPtr);
	if(tmp!=NULL)
		tmp->Next=NULL;
	D->TailPtr=tmp;
	--D->NumItems;
	if(!D->NumItems)
		D->HeadPtr=NULL;
}
DEQUE *D[N];
int n;
short adr[N],padr[N];

int main()
{
	char A[10],B[10];
	short i,j,k,l,t;
	NODE *p;
#ifndef ONLINE_JUDGE
	freopen("A.in","r",stdin);
#endif
	scanf("%d\n",&n);
	for(t=0;t<n;t++)
	{
		D[t]=malloc(sizeof *D[t]);
		D[t]->HeadPtr=D[t]->TailPtr=NULL;
		D[t]->NumItems=0;
		adr[t]=padr[t]=t;
		Push(D[t],t);
	}
	scanf("%s",&A);
	while(strcmp(A,"quit")!=0)
	{
		scanf("%d %s %d\n",&i,&B,&j);
		t=adr[i],k=adr[j];
		if(t==k || i==j)
		{
			scanf("%s",&A);
			continue;
		}
		if(strcmp(A,"move")==0)
		{
			if(strcmp(B,"onto")==0)
			{
				while(D[t]->TailPtr->id!=i)
				{
					Pop(D[t],&l);
					adr[l]=l;
					padr[l]=t;
					Push(D[l],l);
				}
				while(D[k]->TailPtr->id!=j)
				{
					Pop(D[k],&l);
					adr[l]=l;
					padr[l]=k;
					Push(D[l],l);
				}
				Pop(D[t],&l);
				Push(D[k],l);
				assert(l==i);
				adr[i]=k;
				padr[i]=t;
			}
			else
			{
				while(D[t]->TailPtr->id!=i)
				{
					Pop(D[t],&l);
					adr[l]=l;
					padr[l]=t;
					Push(D[l],l);
				}
				Pop(D[t],&l);
				Push(D[k],l);
				assert(l==i);
				adr[i]=k;
				padr[i]=t;
			}
		}
		else
		{
			if(strcmp(B,"onto")==0)
			{
				p=D[k]->HeadPtr;
				while(p->id!=j)
					p=p->Next;
				p=p->Next;
				while(p!=NULL)
				{
					Push(D[padr[p->id]],p->id);
					adr[p->id]=padr[p->id];
					padr[p->id]=k;
					p=p->Next;
				}
				while(D[k]->TailPtr->id!=j)
					Pop(D[k],&l);
				p=D[t]->HeadPtr;
				while(p->id!=i)
					p=p->Next;
				while(p!=NULL)
				{
					Push(D[k],p->id);
					padr[p->id]=t;
					adr[p->id]=k;
					p=p->Next;
				}
				Pop(D[t],&l);
				while(l!=i)
					Pop(D[t],&l);
			}
			else
			{
				p=D[t]->HeadPtr;
				while(p->id!=i)
					p=p->Next;
				while(p!=NULL)
				{
					Push(D[k],p->id);
					adr[p->id]=k;
					padr[p->id]=t;
					p=p->Next;
				}
				Pop(D[t],&l);
				while(l!=i)
					Pop(D[t],&l);
			}
		}
		scanf("%s",&A);
	}
	for(t=0;t<n;t++)
	{
		printf("%d:",t);
		p=D[t]->HeadPtr;
		while(p!=NULL)
		{
			printf(" %d",p->id);
			p=p->Next;
		}
		printf("\n");
	}
	return 0;
}

[emotional blind]

serur,
I dont understand whats ur problem
Do you submit it on Online Judge,
Whats the reply from them?

Its big code, So u only can debug it better than other,
Because it is difficult to understand..

Your program crashes on my machine even for sample input

[serur]

Well, emotional blind, thank you for reply!
My problem is WA...
Recently I solved "Biorythms", and it often occurs to me if there is something in that - in biorythms. If so, I must be on the lowest bound of them all just now.

[emotional blind]

Your code produces wrong output even for sample input.

[serur]

Hi emotional blind!

My code works fine on my machine, so I haven't the slightest idea..
Thank you all the same, I'll fix it some day - when my boirythms will be in full tide

Serkzhan Kazi

[emotional blind]

I have execute your code on my machine
and have such result

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]0:
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9 0
[/OUTPUT]

[emotional blind]

I have execute your code on my machine
and have such result
INPUT

• 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

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

[iostream]

I receive the same report from online-judge when submitting my c++ solution for 101.

The error is:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

I've checked all (local) variables for initialization, but nothing changed.

My program compiles fine on MS Visual Studio 2005 and works fine too (I've tried with sample input, it works fine).
Also, I've used Bloodshed Dev C++ with MinGW compiler and it compiled fine and worked correctly, too.

Has anyone any ideas?
Could you please give me some input that is similar to actual tests?

Here's the code, I apologize there are some duplication... but it works anyway...

Code: Select all

Deleted the code...