OJ Board

Posted: **Tue Jun 20, 2006 2:50 pm**

Hello all,
I just want to say THX to this thread which helped me a lot to solve this problem.

Brathering

Posted: **Tue Jun 20, 2006 2:54 pm**

Or take a look on this thread, it helped me to solve this problem: http://online-judge.uva.es/board/viewtopic.php?t=4019

Posted: **Tue Jun 20, 2006 3:17 pm**

Thanks. I have found the bug in my code. The quit command was not stoping the program.

Posted: **Thu Jun 29, 2006 5:22 pm**

This is my code

Code: Select all

#include <iostream>
#include <string>

using namespace std;

struct boxes {
	int pile;
	int place;
};

struct piles {
	int pileSize;
};

int count = 0;
piles *myPiles;

void initBoxes(boxes *boxvar) {
	int i;
	for (i = 0; i < count; i++) {
		boxvar[i].pile = i;
		boxvar[i].place = 1;
		myPiles[i].pileSize = 1;
	}
}

void moveOnto(int blockA, int blockB, boxes *boxvar) {
	int i, a = 0, pileA = 0, pileB = 0, blockApos = 0;
	pileA = boxvar[blockA].pile;
	pileB = boxvar[blockB].pile;
	blockApos = boxvar[blockA].place;

	if (pileA != pileB) {

		for (i = 0; i < count; i++) {
			if (((boxvar[i].pile == pileA) || (boxvar[i].pile == pileB)) && 
					(boxvar[i].place > blockApos)) {
				myPiles[boxvar[i].pile].pileSize -= 1;
				boxvar[i].pile = i;
				boxvar[i].place = 1;
				myPiles[i].pileSize = 1;
				a++;
			}
		}

		boxvar[blockA].pile = pileB;
		boxvar[blockA].place = myPiles[pileB].pileSize + 1;
		myPiles[pileA].pileSize -= (1 + a);
		myPiles[pileB].pileSize += 1;
	}
}

void moveOver(int blockA, int blockB, boxes *boxvar) {
	int i, a = 0, pileA = 0, pileB = 0, blockApos = 0;
	pileA = boxvar[blockA].pile;
	pileB = boxvar[blockB].pile;
	blockApos = boxvar[blockA].place;

	if (pileA != pileB) {

		for (i = 0; i < count; i++) {
			if ((boxvar[i].pile == pileA) && (boxvar[i].place > blockApos)) {
				boxvar[i].pile = i;
				boxvar[i].place = 1;
				myPiles[i].pileSize = 1;
				a++;
			}
		}

		boxvar[blockA].pile = pileB;
		boxvar[blockA].place = myPiles[pileB].pileSize + 1;
		myPiles[pileA].pileSize -= (1 + a);
		myPiles[pileB].pileSize += 1;
	}
}

void pileOnto(int blockA, int blockB, boxes *boxvar) {
	int i, pileA = 0, pileB = 0, blockApos = 0, blockBpos = 0, pileBsize = 0;
	pileA = boxvar[blockA].pile;
	pileB = boxvar[blockB].pile;
	blockApos = boxvar[blockA].place;
	blockBpos = boxvar[blockB].place;

	if (pileA != pileB) {

		for (i = 0; i <= count; i++) {
			if ((boxvar[i].pile == pileB) && (boxvar[i].place > blockBpos)) {
				boxvar[i].pile = i;
				boxvar[i].place = 1;
				myPiles[i].pileSize += 1;
				myPiles[pileB].pileSize -= 1;
			}
		}

		pileBsize = myPiles[pileB].pileSize;

		for (i = 0; i <= count; i++) {
			if ((boxvar[i].pile == pileA) && (boxvar[i].place >= blockApos)) {
				boxvar[i].pile = pileB;
				boxvar[i].place = (boxvar[i].place - blockApos) + pileBsize + 1;
				myPiles[pileB].pileSize += 1;
				myPiles[pileA].pileSize -= 1;
			}
		}
	}
}

void pileOver(int blockA, int blockB, boxes *boxvar) {
	int i, pileA = 0, pileB = 0, blockApos = 0, pileBsize = 0;
	pileA = boxvar[blockA].pile;
	pileB = boxvar[blockB].pile;
	blockApos = boxvar[blockA].place;
	pileBsize = myPiles[pileB].pileSize;

	if (pileA != pileB) {

		for (i = 0; i <= count; i++) {
			if ((boxvar[i].pile == pileA) && (boxvar[i].place >= blockApos)) {
				boxvar[i].pile = pileB;
				boxvar[i].place = (boxvar[i].place - blockApos) + pileBsize + 1;
				myPiles[pileA].pileSize -= 1;
				myPiles[pileB].pileSize += 1;
			}
		}
	}
}

void doDisplay(boxes *boxvar) {
	int c,i;
	int *display;
	for (i = 0; i < count; i++) {
		cout << i << ":";
		if (myPiles[i].pileSize > 0) {
			display = new int[myPiles[i].pileSize-1];
			for (c = 0; c < count; c++) {
				if (boxvar[c].pile == i) {
					//cout << " " << c;
					display[boxvar[c].place-1] = c;
				}
			}
			for (c = 0; c < myPiles[i].pileSize; c++) {
				cout << " " << display[c];
			}
		} else {
			cout << " ";
		}
		cout << "\n";
	}
}

int main() {
	int i = 0;
	boxes *mybox;
	string input;

	cin >> count;

	mybox = new boxes[count];
	myPiles = new piles[count];
	initBoxes(mybox);

	string action, actfor;
	int from, to = 0;

	while (cin >> action) {
		if (action.compare("quit") == 0) {
			break;
		}
		if (action.compare("display") == 0) {
			doDisplay(mybox);
		} else {
			cin >> from >> actfor >> to;
			if ((from != to) && ((from <= count-1) && (to <= count-1)) &&
					((from >= 0) && (to >= 0))) {
				//cout << action << " " << from << " " << actfor << " " << to << "\n";
				if ((action.compare("move") == 0) && (actfor.compare("onto") == 0)) {
					// Move onto
					moveOnto(from,to,mybox);
				}
				if ((action.compare("move") == 0) && (actfor.compare("over") == 0)) {
					// Move over
					moveOver(from,to,mybox);
				}
				if ((action.compare("pile") == 0) && (actfor.compare("onto") == 0)) {
					// Pile onto
					pileOnto(from,to,mybox);
				}
				if ((action.compare("pile") == 0) && (actfor.compare("over") == 0)) {
					// Pile over
					pileOver(from,to,mybox);
				}
			}
		}
	}

	doDisplay(mybox);

	//system("PAUSE");

	return 0;
}

This gives me a runtime error, and in the email that is sent to me, it states this:

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

Invalid memory reference

Before crash, it ran during 0.062 seconds.

But if I remove the if statement at the pileOver function (the one that checks to see if pileA != pileB) then I get wrong answer.

Can anyone help?
Thanks.

Posted: **Tue Jul 04, 2006 2:40 pm**

Code: Select all

#include<stdio.h>
#include<string.h>
#define INF 29

long point[30],prev[30],next[30],last[30],stk[30],n;

void toinitials(long a)
{
	long x; 
	while(next[a] != INF)
	{
		x = next[a];
		point[x] = x;
		prev[x] = INF;
		last[x] = x;
		stk[x] = x;
		next[a] = INF;
		a = x;
	}
}
void renew(long x,long y)
{
	do
	{	stk[x] = y;
		x = next[x];
	}while(x != INF);
}
void move_onto(long a,long b)
{
	toinitials(a);
	toinitials(b);
	next[b] = a;
	next[a] = INF;
	next[prev[a]] = INF;
	if(point[a] == a)
		point[a]= INF;
	last[stk[a]] = prev[a];
	last[stk[b]] = a ;
	prev[a] = b;
	stk[a] = stk[b];
}

void move_over(long a,long b)
{
	toinitials(a);
	next[last[stk[b]]] = a;
	next[a] = INF;
	next[prev[a]] = INF;
	if(point[a] == a)
		point[a] = INF ;
	last[stk[a]] = prev[a];
		prev[a]= last[stk[b]];
	last[stk[b]] = a;
	stk[a] = stk[b];
}
void pile_onto(long a,long b)	
{
	toinitials(b);
	next[b] = a;
	next[prev[a]] = INF;
	last[b] = last[stk[a]];
	if(point[a] = a)
	{	point[a] = INF;
		last[a] = INF;
	}
	else
		last[stk[a]] = prev[a];
	prev[a] = b;
	renew(a,stk[b]);
}

void pile_over(long a,long b)
{
	next[last[stk[b]]] = a;
	next[prev[a]] = INF;
	prev[a] = last[b];
	last[b] = last[stk[a]];
	if(point[a]==a)
	{	point[a] = INF;
		last[a] = INF;
	}
	else
		last[stk[a]] = prev[a];
	renew(a,stk[b]);
}

void main()
{
	//freopen("101.in","r",stdin);
	//freopen("101.out","w",stdout);
	char s1[100],s2[100];
	long a,b,i,m;
	scanf("%ld",&n);
	for(i=0;i<n;i++)
	{
		point[i] = i;		prev[i] = INF;	next[i] = INF;	last[i] = i;	stk[i] = i;
	}
	while(scanf(" %s",s1)==1)
	{
		if(strcmp(s1,"quit")==0)
			break;
		scanf("%ld %s %ld",&a,s2,&b);
		if(a == n || stk[a]==stk[b] || a>=n || a< 0 || b>=n || b< 0)
			continue;
		if(strcmp(s1,"move")==0)
		{
			if(strcmp(s2,"onto")==0)
				move_onto(a,b);
			else if(strcmp(s2,"over")==0)
				move_over(a,b);
		}
		else if(strcmp(s1,"pile")==0)
		{	if(strcmp(s2,"onto")==0)
				pile_onto(a,b);
			else if(strcmp(s2,"over")==0)
				pile_over(a,b);
		}
	}
	for(i = 0; i < n; i++)
	{
		printf("%2ld: ",i);
		m = point[i];
		while(m != INF)
		{
			printf(" %ld",m);
			m = next[m];
		}
		printf("\n");
	}
}

[/code]

Posted: **Tue Jul 04, 2006 8:15 pm**

first there may be mutiple set of inputs, ex:

Code: Select all

10
...
...
quite
5
..
..
quite

about TLE:
try to solve it using linklist.

Posted: **Wed Jul 05, 2006 7:12 am**

Chung Ha, Yun wrote:
gits wrote:my code gives:
...
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

Thx. That one solved it for me

Must learn to read the ENTIRE problem description

Posted: **Tue Jul 18, 2006 5:08 pm**

Why i get TLE ?

My code is:
variable description
arr[p][0] = Block number below the block p, -1 for no block
arr[p][1] = Block number above the block p, -1 for no block
start[c] = bottom most block number in column c. -1 for no block
col[p] = Column number in which block p is present.

Code: Select all

#include<stdio.h>

int arr[25][2];
int start[25];
int col[25];

int main()
{
	int i,j,k,l;
	int n;
	char str1[20],str2[20];
	int a,b;
while(1)
{
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		arr[i][0]=-1;	
		arr[i][1]=-1;
		start[i]=i;
		col[i]=i;
	}

	scanf("%s",str1);
	while(strcmp(str1,"quit")!=0)
	{
		scanf("%d %s %d",&a,str2,&b);
		if(a==b || col[a]==col[b])
		{
			scanf("%s",str1);
			continue;
		}
		if(strcmp(str1,"move")==0)
		{
			i=arr[a][1];
			while(i!=-1)
			{
				j=arr[i][1];
				arr[arr[i][0]][1]=-1;
				arr[i][0]=-1;
				col[i]=i;
				start[i]=i;
				i=j;
			}
		}
		if(strcmp(str2,"onto")==0)
		{
			i=arr[b][1];
			while(i!=-1)
			{
				j=arr[i][1];
				arr[arr[i][0]][1]=-1;
				arr[i][0]=-1;
				col[i]=i;
				start[i]=i;
				i=j;
			}
		}
		i=b;
		while(arr[i][1]!=-1)
			i=arr[i][1];
		if(arr[a][0]==-1)
		{
			start[a]=-1;
		}
		else
		{
			arr[arr[a][0]][1]=-1;
		}
		arr[a][0]=i;
		arr[i][1]=a;
		col[a]=col[b];
		scanf("%s",str1);
	}
	for(i=0;i<n;i++)
	{
		printf("%d:",i);
		j=start[i];
		while(j!=-1)
		{
			printf(" %d",j);
			j= arr[j][1];
		}
		printf("\n");
		
	}
}
	return 0;
}

Posted: **Sun Jul 23, 2006 12:41 pm**

the code works fine on my pc but gives runtime error on submission....

Code: Select all

# include <iostream.h>
# include <string.h>
using namespace std;
struct no
	{int n;no *u,*d;};
no *Z[26],*X[26];int n,Y[26];
void rem(int a);
void pr();
int main()
	{int a,b;char s[5],s2[5];no *t,*t2;
	 cin>>n;
	 for(a=0;a<n;a++)
		{Z[a]=NULL;Z[a]=new no;Z[a]->u=NULL;
		 Z[a]->n=a;Z[a]->d=NULL;
		 Y[a]=a;X[a]=Z[a];
		}
	 while(1)
		{cin>>s;if(strcmp(s,"quit")==0) break;
		 cin>>a>>s2>>b;
		 if(a==b || a<0 || a>=n || b<0 || b>=n || Y[a]==Y[b]) continue;
		 if(strcmp(s,"move")==0 && strcmp(s2,"onto")==0)
			{rem(a);rem(b);t=X[Y[a]];
			 X[Y[a]]=t->d;if(t->d==NULL) Z[Y[a]]=NULL; else t->d->u=NULL;
			 if(X[Y[b]]==NULL) Z[Y[b]]=t; else X[Y[b]]->u=t;
			 t->d=X[Y[b]];X[Y[b]]=t;
			 Y[a]=b;
			}
		 else if(strcmp(s,"move")==0 && strcmp(s2,"over")==0)
			{rem(a);t=X[Y[a]];
			 X[Y[a]]=t->d;if(t->d==NULL) Z[Y[a]]=NULL; else t->d->u=NULL;
			 if(X[Y[b]]==NULL) Z[Y[b]]=t; else X[Y[b]]->u=t;
			 t->d=X[Y[b]];X[Y[b]]=t;
			 Y[a]=b;
			}
		 else if(strcmp(s,"pile")==0 && strcmp(s2,"onto")==0)
			{rem(b);t2=X[Y[a]];
			 for(t=X[Y[a]];;t=t->d)
				{if(t->n==a) break;
				 Y[t->n]=Y[b];
				}
			 X[Y[a]]=t->d;if(t->d==NULL) Z[Y[a]]=NULL; else t->d->u=NULL;
			 if(X[Y[b]]==NULL) Z[Y[b]]=t; else X[Y[b]]->u=t;
			 t->d=X[Y[b]];X[Y[b]]=t2;
			 Y[a]=b;
			}
		 else if(strcmp(s,"pile")==0 && strcmp(s2,"over")==0)
			{t2=X[Y[a]];
			 for(t=X[Y[a]];;t=t->d)
				{if(t->n==a) break;
				 Y[t->n]=Y[b];
				}
			 X[Y[a]]=t->d;if(t->d==NULL) Z[Y[a]]=NULL; else t->d->u=NULL;
			 if(X[Y[b]]==NULL) Z[Y[b]]=t; else X[Y[b]]->u=t;
			 t->d=X[Y[b]];
			 X[Y[b]]=t2;Y[a]=b;
			}
		}pr();
	 for(a=0;a<n;a++)
		for(t=Z[a];t!=NULL;)
			{if(t->u==NULL) delete t;
			 t=t->u;if(t!=NULL && t->d!=NULL) delete t->d;
			}
	 return 0;
	}
void rem(int a)
	{no *t=X[Y[a]];
	 while(t->n!=a)
		{X[Y[a]]=t->d;t->d->u=NULL;
		 if(X[t->n]==NULL) Z[t->n]=t; X[t->n]->u=t;
		 t->d=X[t->n];X[t->n]=t;
		 Y[t->n]=t->n;
		}
	}
void pr()
	{int a;no *t;
	 for(a=0;a<n;a++)
		{cout<<a<<":";
		 for(t=Z[a];t!=NULL;t=t->u)
			cout<<" "<<t->n;
		 cout<<"\n";
		}
	}

[/code]

Posted: **Mon Jul 31, 2006 7:34 am**

101 is a worst type ad hoc problem!
I can remember I had a lots of RE and WA in this problem.

Try to increment your array size and check where you have called some memory what is actually not present. Your code is quite messy, so I cant do that.. and if these two dont work.. plz recode your code.. that will solve it!

Posted: **Tue Aug 08, 2006 10:38 pm**

here is my code:

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

int main (void){
	int num;
    cin >> num;
    vector <int> nista;
	vector <vector <int> > pozicije (num, nista);
	for (int i=0; i<num; i++){
		pozicije[i].push_back(i);
	}
	while (true){
		string  com1, com2;
		int koga, kam;
		cin >> com1;
		if (com1=="quit") break;
		else cin >> koga >> com2 >> kam;
		if (koga==kam) continue;
		
		bool k3=false;
		for (int i=0; i<pozicije.size(); i++){
			bool k1=false, k2=false;
			for (int j=0; j<pozicije[i].size(); j++){
				if (pozicije[i][j]==koga) k1=true;
				if (pozicije[i][j]==kam) k2=true;
			}
			if (k1==true && k2==true) k3=true;
		}
		if (k3==true) continue;
				
		if (com1=="move" && com2=="onto"){
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==koga){
						pozicije[i].erase(pozicije[i].begin()+j);
						naso=true;
						for (int k=j; k<pozicije[i].size();){
							pozicije[pozicije[i][j]].push_back(pozicije[i][j]);
							pozicije[i].erase(pozicije[i].begin()+j);
						}
					}
				}
				if (naso==true) break;
			}
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==kam){
						for (int k=j+1; k<pozicije[i].size();){
							pozicije[pozicije[i][j]].push_back(pozicije[i][j]);
							pozicije[i].erase(pozicije[i].begin()+j);
						}				
						pozicije[i].insert(pozicije[i].begin()+j+1, koga);
						break;
						naso=true;
					}
				}
				if (naso==true) break;
			}		
		}
		
		else if (com1=="move" && com2=="over"){
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==koga){
						pozicije[i].erase(pozicije[i].begin()+j);
						naso=true;
						for (int k=j; k<pozicije[i].size();){
							pozicije[pozicije[i][j]].push_back(pozicije[i][j]);
							pozicije[i].erase(pozicije[i].begin()+j);
						}
					}
				}
				if (naso==true) break;
			}
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==kam){
						naso=true;
						pozicije[i].push_back(koga);
						break;
					}
				}
				if (naso==true) break;
			}
		}
		
		else if (com1=="pile" && com2=="onto"){
			vector <int> premjestam;
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==koga){
						naso=true;
						for (int k=j; k<pozicije[i].size();){
							premjestam.push_back(pozicije[i][j]);
							if (pozicije[i][j]==kam) break;
							pozicije[i].erase(pozicije[i].begin()+j);
						}
					}
				}
				if (naso==true) break;
			}
			
			bool premjesti=false;
			for (int i=0; i<pozicije.size(); i++){
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==kam){
						
						for (int k=j+1; k<pozicije[i].size();){
							pozicije[pozicije[i][j+1]].push_back(pozicije[i][j+1]);
							pozicije[i].erase(pozicije[i].begin()+j+1);
						}
						for (int l=0, k=j+1; l<premjestam.size(); k++, l++){
							pozicije[i].insert(pozicije[i].begin()+k, premjestam[l]);
						}
						premjesti=true;
						break;
					}
				}
				if (premjesti==true) break;
			}
		}
		
		else if (com1=="pile" && com2=="over"){
			vector <int> premjestam;
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==koga){
						naso=true;
						for (int k=j; k<pozicije[i].size();){	
							premjestam.push_back(pozicije[i][j]);
							if (pozicije[i][j]==kam) break;
							pozicije[i].erase(pozicije[i].begin()+j);
						}
					}
				}
				if (naso==true) break;
			}
			for (int i=0; i<pozicije.size(); i++){
				bool naso=false;
				for (int j=0; j<pozicije[i].size(); j++){
					if (pozicije[i][j]==kam){
						naso=true;
						for (int k=0; k<premjestam.size(); k++) pozicije[i].push_back(premjestam[k]);
						break;
					}
				}
				if (naso==true) break;
			}	
		}
			
	}
	
	for (int i=0; i<num; i++){
		cout << i << ": ";
		for (int j=0; j<pozicije[i].size(); j++){
			cout << pozicije[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

tnx for help

Posted: **Sun Aug 20, 2006 12:47 pm**

You should use functions/subroutines in your program, or OOP. Here is the example of what it should like in Python (feel free to translate it into C++):

Code: Select all

# Program that solves The Blocks Problem 
# http://acm.uva.es/p/v1/101.html

# class Robot that solves The Blocks Problem 
class Robot:
	# Class members:
	#	blocks	blocks - list of stacks
	#	n		number of blocks on a table
	
	# constructor
	#	initializes an array of stacks "blocks" with blocks 1, 2,..., n
	#	in: n - number of blocks
	def __init__(self, size):
		self.n = size
		self.blocks = [[i] for i in range(size)]			
	
	# methos that prints the Robot object with 'print' command
	def __str__(self):
		tempStr = ""
		for i in range(self.n):
			tempStr += str(i)+":"
			for el in self.blocks[i]:
				tempStr += " "+str(el)
			tempStr += "\n"
		return tempStr
	
	# finds position 0..n-1 in which element el is
	# in: el - element
	#out: position of the block (0..n-1)
	def getPosition(self, el):
		for i in range(self.n):
			if el in self.blocks[i]:
				return i
	
	# moves elements on top of el in position pos to their initial position
	# in: el - element	
	# in: pos - position
	def moveToInitial(self, el, pos):
		while True:
			popped = self.blocks[pos].pop()
			if popped != el:
				self.blocks[popped].append(popped)
			else:
				self.blocks[pos].append(popped)
				break
				
	# moves a onto/over b
	# in: s - string holding 'onto'/'over'	
	# in: a, b - blocks
	def move(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)	
		self.moveToInitial(a, aPos)
		if s == 'onto':
			self.moveToInitial(b, bPos)		
		self.blocks[bPos].append(self.blocks[aPos].pop())
		
	# piles a onto/over b
	# in: s - string holding 'onto'/'over'		
	# in: a, b - blocks
	def pile(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)
		if s == 'onto':
			self.moveToInitial(b, bPos)
		tempStack = []
		while True:
			el = self.blocks[aPos].pop()
			tempStack.append(el)
			if el == a:
				break
		while tempStack != []:
			self.blocks[bPos].append(tempStack.pop())

	
file = open('input.txt')
robot = Robot(int(file.readline().strip()))
for line in file:
	s = line.strip().split(' ')
	if s[0] == 'move':
		robot.move(s[2], int(s[1]), int(s[3]))		
	elif s[0] == 'pile':
		robot.pile(s[2], int(s[1]), int(s[3]))
	elif s[0] == 'quit':
		break
file.close()
print robot

Posted: **Sun Aug 20, 2006 12:50 pm**

it will look like this:

Code: Select all

class Robot:

	def __init__(self, size):
		self.n = size
		self.blocks = [[i] for i in range(size)]	
		
	def __str__(self):
		tempStr = ""
		for i in range(self.n):
			tempStr += str(i)+":"
			for el in self.blocks[i]:
				tempStr += " "+str(el)
			tempStr += "\n"
		return tempStr
	
	def getPosition(self, el):
		for i in range(self.n):
			if el in self.blocks[i]:
				return i

	def moveToInitial(self, el, pos):
		while True:
			popped = self.blocks[pos].pop()
			if popped != el:
				self.blocks[popped].append(popped)
			else:
				self.blocks[pos].append(popped)
				break

	def move(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)	
		self.moveToInitial(a, aPos)
		if s == 'onto':
			self.moveToInitial(b, bPos)		
		self.blocks[bPos].append(self.blocks[aPos].pop())
		
	def pile(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)
		if s == 'onto':
			self.moveToInitial(b, bPos)
		tempStack = []
		while True:
			el = self.blocks[aPos].pop()
			tempStack.append(el)
			if el == a:
				break
		while tempStack != []:
			self.blocks[bPos].append(tempStack.pop())

	
file = open('input.txt')
robot = Robot(int(file.readline().strip()))
for line in file:
	s = line.strip().split(' ')
	if s[0] == 'move':
		robot.move(s[2], int(s[1]), int(s[3]))		
	elif s[0] == 'pile':
		robot.pile(s[2], int(s[1]), int(s[3]))
	elif s[0] == 'quit':
		break
file.close()
print robot

PS: use comments in your programs, so that other people can understand it

Posted: **Sun Aug 20, 2006 12:58 pm**

Your code will look better if you use comments/subroutines. Also, this problem would be solved more efficiently using stacks. Here is the example of the Python program (feel free to convert it to C++):

Code: Select all

# Program that solves The Blocks Problem 
# http://acm.uva.es/p/v1/101.html

# class Robot that solves The Blocks Problem 
class Robot:
	# Class members:
	#	blocks	blocks - list of stacks
	#	n		number of blocks on a table
	
	# constructor
	#	initializes an array of stacks "blocks" with blocks 1, 2,..., n
	#	in: n - number of blocks
	def __init__(self, size):
		self.n = size
		self.blocks = [[i] for i in range(size)]			
	
	# methos that prints the Robot object with 'print' command
	def __str__(self):
		tempStr = ""
		for i in range(self.n):
			tempStr += str(i)+":"
			for el in self.blocks[i]:
				tempStr += " "+str(el)
			tempStr += "\n"
		return tempStr
	
	# finds position 0..n-1 in which element el is
	# in: el - element
	#out: position of the block (0..n-1)
	def getPosition(self, el):
		for i in range(self.n):
			if el in self.blocks[i]:
				return i
	
	# moves elements on top of el in position pos to their initial position
	# in: el - element	
	# in: pos - position
	def moveToInitial(self, el, pos):
		while True:
			popped = self.blocks[pos].pop()
			if popped != el:
				self.blocks[popped].append(popped)
			else:
				self.blocks[pos].append(popped)
				break
				
	# moves a onto/over b
	# in: s - string holding 'onto'/'over'	
	# in: a, b - blocks
	def move(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)	
		self.moveToInitial(a, aPos)
		if s == 'onto':
			self.moveToInitial(b, bPos)		
		self.blocks[bPos].append(self.blocks[aPos].pop())
		
	# piles a onto/over b
	# in: s - string holding 'onto'/'over'		
	# in: a, b - blocks
	def pile(self, s, a, b):
		aPos = self.getPosition(a)
		bPos = self.getPosition(b)
		if s == 'onto':
			self.moveToInitial(b, bPos)
		tempStack = []
		while True:
			el = self.blocks[aPos].pop()
			tempStack.append(el)
			if el == a:
				break
		while tempStack != []:
			self.blocks[bPos].append(tempStack.pop())

	
file = open('input.txt')
robot = Robot(int(file.readline().strip()))
for line in file:
	s = line.strip().split(' ')
	if s[0] == 'move':
		robot.move(s[2], int(s[1]), int(s[3]))		
	elif s[0] == 'pile':
		robot.pile(s[2], int(s[1]), int(s[3]))
	elif s[0] == 'quit':
		break
file.close()
print robot

Posted: **Fri Sep 01, 2006 7:57 am**

#include<iostream>
#include<cstring>
//#include<fstream>
using namespace std;
//ifstream fin("block.txt");

int block[25][25];

void FindDimen(int k,int *Find_i,int *Find_j)
{
for(int i=0;i<25;i++)
for(int j=0;j<25;j++)
if(block[j] == k)
{
*Find_i = i;
*Find_j = j;
}

}

int main()
{
int n,c;
char word1[5];
char word2[5];
int num1,num2;
int dimen1,dimen2,dimen3,dimen4;
int i,j,k;

for(i=0;i<25;i++)
for(j=0;j<25;j++)
block[j] = -1;

cin >> n;

for(k=0;k<n;k++)
block[k][0] = k;

cin >> word1;

while(strcmp(word1,"quit") != 0)
{

cin >> num1 >> word2 >> num2;

FindDimen(num1,&dimen1,&dimen2);
FindDimen(num2,&dimen3,&dimen4);
if(num1 != num2 && dimen1 != dimen3)
if(strcmp(word1,"move") == 0)
{

if(strcmp(word2,"onto") == 0)
{
for(i = dimen2+1;i<n;i++)
if(block[dimen1] != -1)
{
block[block[dimen1]][0] = block[dimen1];
block[dimen1] = -1;

}

for(i = dimen4+1;i<n;i++)
if(block[dimen3] != -1)
{
block[block[dimen3]][0] = block[dimen3];
block[dimen3] = -1;

}

block[dimen1][dimen2] = -1;
block[dimen3][dimen4+1] = num1;
}
else
{

for(i = dimen2+1;i<n;i++)
if(block[dimen1][i] != -1)
{
block[block[dimen1][i]][0] = block[dimen1][i];
block[dimen1][i] = -1;

}
c=0;
while(block[dimen3][dimen4+1] != -1)
{
dimen4++;

}

block[dimen1][dimen2] = -1;
block[dimen3][dimen4+1] = num1;

}

}
else
{
if(strcmp(word1,"pile") == 0)
{
if(strcmp(word2,"onto") == 0)
{

for(i = dimen4+1;i<n;i++)
if(block[dimen3][i] != -1)
{
block[block[dimen3][i]][0] = block[dimen3][i];
block[dimen3][i] = -1;

}

c = 0;
for(i = dimen4+1;i<n;i++)

{
block[dimen3][i] = block[dimen1][dimen2+c];
block[dimen1][dimen2+c] = -1;
c++;
}

}
else
{

while(block[dimen3][dimen4+1] != -1)
{
dimen4++;

}

c = 0;
for(i = dimen4+1;i<n;i++)
{
block[dimen3][i] = block[dimen1][dimen2+c];
block[dimen1][dimen2+c] = -1;
c++;
}

}// end if "onto"

}//end if "pile"

}//end if "move"

cin >> word1;

}// end while

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

return 0;
}

OJ Board

101 - The Blocks Problem

Problem 101 RE

101 why TLE ?

Re: ^^

Why i get TLE ?

runtime error in 101 - invalidmemor refrence

101, why TLE?

your code is too complicated

and without comments

Use comments/subrountines/stacks

101 wa ?