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

tudmir
New poster
Posts: 1
Joined: Thu May 30, 2013 1:55 am

Problem 101 Java Wrong Answer

Post by tudmir » Thu May 30, 2013 2:03 am

I am solving the problem 101. I think that my solution is correct because every test I have passed is successful.
My problem is that I have uploud the file to the judge and it shows me a "Wrong Answer" error.
The code that I have programmed is here:

Code: Select all

import java.io.*;
import java.util.*;

class Main {
	int mesa[][];

	static String ReadLn(int maxLongitud){
		byte linea[]=new byte[maxLongitud];
		int longitud=0,caracter=-1;

		try{
			while(longitud<maxLongitud){
				caracter=System.in.read();

				if((caracter<0) || (caracter=='\n')){
					break;
				}
				linea[longitud++]+=caracter;
			}
		}catch(IOException e){
			return null;
		}
		return (new String(linea,0,longitud));
	}	
	
	public static void main(String[] args) {
		Main programa=new Main();
		programa.lanzar();
	}
	
	void lanzar(){
		String linea;
		StringTokenizer idata;
		int n, a, b;
		posicion posA, posB;
		String instruccion;
		String tipoInstruccion;

		linea=ReadLn(255);
		idata=new StringTokenizer(linea);
		n=Integer.parseInt(idata.nextToken());

		mesa=new int[n][];
		for(int i=0;i<n;i++){
			mesa[i]=new int[1];
			mesa[i][0]=i;
		}

		do{
			linea=ReadLn(255);
			idata=new StringTokenizer(linea);

			instruccion=idata.nextToken();

			if(!instruccion.equals("quit")){
				a = Integer.parseInt(idata.nextToken());
				tipoInstruccion=idata.nextToken();
				b = Integer.parseInt(idata.nextToken());

				if((a!=b)){
					posA=buscar(a);
					posB=buscar(b);

					if(posA.getPila()!=posB.getPila()){
						if(instruccion.equals("move")){
							if(tipoInstruccion.equals("over")){
								moveover(posA,posB);
							}else if(tipoInstruccion.equals("onto")){
								moveonto(posA,posB);
							}
						}else if(instruccion.equals("pile")){
							if(tipoInstruccion.equals("over")){
								pileover(posA,posB);
							}else if(tipoInstruccion.equals("onto")){
								pileonto(posA,posB);
							}							
						}
					}
				}
			}
		}while(!instruccion.equals("quit"));
		mostrar();
	}
	
	void mostrar(){
		String linea;

		for(int i=0;i<mesa.length;i++){
			linea=i + ":";
			for(int j=0;j<mesa[i].length;j++){
				linea+=" " + mesa[i][j];
			}
			System.out.println(linea);
		}
	}

	posicion buscar(int bloque){
		int pila=0, altura=0;
		boolean encontrado=false;
		for(int i=0;i<mesa.length && !encontrado;i++){
			for(int j=0;j<mesa[i].length && !encontrado;j++){
				if(mesa[i][j]==bloque){
					encontrado=true;
					pila=i;
					altura=j;
				}
			}
		}
		return new posicion(pila,altura);
	}
	
	void moveover(posicion posa,posicion posb){
		int pilaauxB[],pilaauxA[];
		int i;
		pilaauxB=new int[mesa[posb.getPila()].length+1];

		for(i=0;i<mesa[posb.getPila()].length;i++){
			pilaauxB[i]=mesa[posb.getPila()][i];
		}
		pilaauxB[i]=mesa[posa.getPila()][posa.getAltura()];
		mesa[posb.getPila()]=pilaauxB;

		pilaauxA=new int[mesa[posa.getPila()].length-1];

		for(i=0;i<posa.getAltura();i++){
			pilaauxA[i]=mesa[posa.getPila()][i];
		}

		for(i=posa.getAltura()+1;i<mesa[posa.getPila()].length;i++){
			pilaauxA[i-1]=mesa[posa.getPila()][i];
		}

		mesa[posa.getPila()]=pilaauxA;		
	}
	
	void pileover(posicion posa,posicion posb){
		int pilaauxA[], pilaauxB[];
		int i;

		pilaauxB=new int[mesa[posb.getPila()].length +
		         mesa[posa.getPila()].length - posa.getAltura()];
		pilaauxA=new int[posa.getAltura()];

		for(i=0;i<mesa[posb.getPila()].length;i++){
			pilaauxB[i]=mesa[posb.getPila()][i];
		}		

		for(i=0;i<posa.getAltura();i++){
			pilaauxA[i]=mesa[posa.getPila()][i];
		}

		for(int j=i;j<mesa[posa.getPila()].length;j++){
			pilaauxB[mesa[posb.getPila()].length + j - i] =
				mesa[posa.getPila()][j];
		}

		mesa[posa.getPila()]=pilaauxA;
		mesa[posb.getPila()]=pilaauxB;		
	}
	
	void moveonto(posicion posa,posicion posb){
		int pilaauxA[], pilaauxB[];
		int contB, i;

		pilaauxA=new int[mesa[posa.getPila()].length-1];
		pilaauxB=new int[mesa[posb.getPila()].length+1];

		for(contB=0;contB<=posb.getAltura();contB++){
			pilaauxB[contB]=mesa[posb.getPila()][contB];
		}

		pilaauxB[contB]=mesa[posa.getPila()][posa.getAltura()];

		for(i=contB+1;i<pilaauxB.length; i++){
			pilaauxB[i]=mesa[posb.getPila()][i-1];
		}

		for(i=0;i<posa.getAltura();i++){
			pilaauxA[i]=mesa[posa.getPila()][i];
		}

		for(i=posa.getAltura()+1;i<mesa[posa.getPila()].length;i++){
			pilaauxA[i-1]=mesa[posa.getPila()][i];
		}

		mesa[posa.getPila()]=pilaauxA;
		mesa[posb.getPila()]=pilaauxB;
	}
	
	void pileonto(posicion posa,posicion posb){
		int pilaauxA[],pilaauxB[];
		int contB,contA,i;

		pilaauxB=new int[mesa[posb.getPila()].length +
		         mesa[posa.getPila()].length - posa.getAltura()];

		pilaauxA=new int[posa.getAltura()];

		for(contA=0;contA<posa.getAltura();contA++){
			pilaauxA[contA]=mesa[posa.getPila()][contA];
		}

		for(contB=0;contB<=posb.getAltura();contB++){
			pilaauxB[contB]=mesa[posb.getPila()][contB];
		}

		for(i=posa.getAltura();i<mesa[posa.getPila()].length;i++){
			pilaauxB[contB++]=mesa[posa.getPila()][i];
		}

		for(i=contB;i<pilaauxB.length;i++){
			pilaauxB[i]=mesa[posb.getPila()][posb.getAltura()+i-contB+1];
		}

		mesa[posa.getPila()]=pilaauxA;
		mesa[posb.getPila()]=pilaauxB;
	}

	class posicion{
		int pila;
		int altura;
		posicion(int pila,int altura){
			this.pila=pila;
			this.altura=altura;
		}
		int getPila(){
			return pila;
		}
		int getAltura(){
			return altura;
		}
	}
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Problem 101 Java Wrong Answer

Post by brianfry713 » Tue Jun 11, 2013 12:52 am

Check input and AC output for thousands of problems on uDebug!

dhdersch
New poster
Posts: 1
Joined: Thu Jul 25, 2013 11:51 pm

Re: 101 , Code in C++, Runtime error

Post by dhdersch » Thu Jul 25, 2013 11:55 pm

Well, sadly, I am getting WA using C++. I've tried many different sample inputs provided here on the board, and I still haven't found what the problem is. Here is my code...

Code: Select all

// uvaproblems.cpp : main project file.


#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;


class Coordinate {
	
	public:
		int row;
		int col;

	Coordinate(int _row, int _col) {
		row = _row;
		col = _col;
	}

		
};


class TheBlocksProblem {

	private:
		int _numBlocks;
		vector<vector<int> > _grid;
		vector<Coordinate*> _locations;


	public: 
	
		TheBlocksProblem(int numberOfBlocks) {
			_numBlocks = numberOfBlocks;
			_grid = vector<vector<int> >(numberOfBlocks);
			_locations = vector<Coordinate*>(numberOfBlocks);

			for (int i = 0; i < numberOfBlocks; ++i) {
				_grid[i] = vector<int>(numberOfBlocks);
				_grid[i][0] = i;
				_locations[i] = new Coordinate(i, 0);
				for (int j = 1; j < numberOfBlocks; ++j) {
					_grid[i][j] = -1;
				}
			}
		}


		void MoveAontoB(int a, int b){
			Coordinate* aCoord = _locations[a];
			Coordinate* bCoord = _locations[b];
			if (this->IsInvalidCommand(aCoord, bCoord)) {
				return;
			}
			this->ReturnBlocksAbove(a);
			this->ReturnBlocksAbove(b);

			
			_grid[aCoord->row][aCoord->col] = -1;

			
			aCoord->row = bCoord->row;
			aCoord->col = bCoord->col + 1;
			_grid[aCoord->row][aCoord->col] = a;

		}

		void MoveAoverB(int a, int b){
			Coordinate* aCoord = _locations[a];
			Coordinate* bCoord = _locations[b];
			if (this->IsInvalidCommand(aCoord, bCoord)) {
				return;
			}
			this->ReturnBlocksAbove(a);

			
			_grid[aCoord->row][aCoord->col] = -1;

			
			for(int i = bCoord->col + 1; i < _numBlocks; ++i) {
				if (_grid[bCoord->row][i] == -1) {
					_grid[bCoord->row][i] = a;
					aCoord->row = bCoord->row;
					aCoord->col = i;
					return;
				}
			}


		}

		void PileAontoB(int a, int b){
			Coordinate* aCoord = _locations[a];
			Coordinate* bCoord = _locations[b];
			if (this->IsInvalidCommand(aCoord, bCoord)) {
				return;
			}
			this->ReturnBlocksAbove(b);



			int origRow = aCoord->row;
			int newRow = bCoord->row;
			int newFirstCol = bCoord->col + 1;

			for (int i = aCoord->col; i < _numBlocks && _grid[origRow][i] != -1; ++i) {
				this->MoveBlockToEndOfRow(_grid[origRow][i], newRow, newFirstCol);
				++newFirstCol;
			}

		}



		void PileAoverB(int a, int b){
			Coordinate* aCoord = _locations[a];
			Coordinate* bCoord = _locations[b];
			if (this->IsInvalidCommand(aCoord, bCoord)) {
				return;
			}

			int origRow = aCoord->row;
			int newRow = bCoord->row;

			int newFirstCol = bCoord->col + 1;

			for (int i = aCoord->col; i < _numBlocks && _grid[origRow][i] != -1; ++i) {
				this->MoveBlockToEndOfRow(_grid[origRow][i], newRow, newFirstCol);
				++newFirstCol;
			}
		}



		void PrintWithEmpties() {
			
			for (int i = 0; i < _numBlocks; ++i) {
				cout << i << ": ";
				for (int j = 0; j < _numBlocks; ++j) {
					cout << _grid[i][j] << " ";;
				}
				cout << endl;
			}

		}

		void PrintNoEmpties() {
			
			for (int i = 0; i < _numBlocks; ++i) {
				cout << i << ":";
				for (int j = 0; j < _numBlocks; ++j) {
					if (_grid[i][j] == -1) {
						break;
					}
					cout <<  " " << _grid[i][j] ;
				}

				cout << endl;

			}

		}

		void PrintLocations() {
			for (int i = 0; i < _locations.size(); ++i) {
				cout << i << ": (" << _locations[i]->row << "," << _locations[i]->col << ")" << endl;

			}

		}

	private:
		void ReturnBlocksAbove(int blockNum) {
			Coordinate* coord = _locations[blockNum];

			for (int i = coord->col + 1; i < _numBlocks; ++i){

				if (_grid[coord->row][i] == -1) {
					return;
				}

				this->MoveSingleBlockBack(_grid[coord->row][i]);

			}

		}

		void MoveSingleBlockBack(int blockNum) {

			Coordinate* coord = _locations[blockNum];
			_grid[coord->row][coord->col] = -1;

			for (int i = 0; i < _numBlocks; ++i) {
				if (_grid[blockNum][i] == -1) {

					_grid[blockNum][i] = blockNum;
					coord->row = blockNum;
					coord->col = i;
					return;
				}
			}
		}

	void MoveBlockToEndOfRow(int blockNum, int newRow, int startCol) {
			Coordinate* blockCoord = _locations[blockNum];
			_grid[blockCoord->row][blockCoord->col] = -1;

			for (int i = startCol; i < _numBlocks; ++i) {
				if (_grid[newRow][i] == -1) {
					_grid[newRow][i] = blockNum;
					blockCoord->row = newRow;
					blockCoord->col = i;
					return;

				}
			}

		}
	bool IsInvalidCommand(Coordinate* a, Coordinate* b) {
		if (a->row == b->row || _grid[a->row][a->col] == _grid[b->row][b->col]) {
			return true;
		}
	}

};



int main()
{
	int n;

	cin >> n;
	TheBlocksProblem *prob = new TheBlocksProblem(n);
	string line = "";
	string firstWord = "";
	string secondWord = "";
	int aNum = -1;
	int bNum = -1;
	
	while (true) {


		std::getline (std::cin,line);
		stringstream ss;
		ss << line;

	
		ss >> firstWord ; 
		if (firstWord == "quit") {
			break;
		}
		ss>> aNum >> secondWord >> bNum;

		if (firstWord == "move" && secondWord == "onto") {
			prob->MoveAontoB(aNum, bNum);
		} else if (firstWord == "move" && secondWord == "over") {
			prob->MoveAoverB(aNum, bNum);

		} else if (firstWord == "pile" && secondWord == "onto") {
			prob->PileAontoB(aNum, bNum);

		} else if (firstWord == "pile" && secondWord == "over") {
			prob->PileAoverB(aNum, bNum);
		}
	}


	prob->PrintNoEmpties();
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 , Code in C++, Runtime error

Post by brianfry713 » Sat Jul 27, 2013 3:28 am

Doesn't match the sample I/O
Check input and AC output for thousands of problems on uDebug!

dennisorz
New poster
Posts: 9
Joined: Wed Aug 14, 2013 6:04 pm

101 - The Blocks Problem-wrong answer

Post by dennisorz » Wed Aug 21, 2013 10:54 am

Please help me find bug!

Code: Select all

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
vector<unsigned int> block[25];
int Index[25];

void print(int N){
	for(int i=0;i<N;i++){
		cout<<i<<":"; 
		for(int j=0;j<block[i].size();j++)
			cout <<" "<< block[i][j];
		cout<<endl; 
	}
		
}

void Clear(int p){
	int F=0;
	int end=block[Index[p]].size()-1;

	for(int i=0;i<block[Index[p]].size();i++){
		if(block[Index[p]][i]==p)
			F=i;
	}
	for(int i=end;i>F;i--){
		Index[block[Index[p]][i]]=block[Index[p]][i];
		block[block[Index[p]][i]].push_back(block[Index[p]][i]);
		block[Index[p]].pop_back();
	}
}
 
void Move(int a,int b){
	vector<unsigned int> temp;
	int F=0;
	int end=block[Index[a]].size()-1;
	for(int i=0;i<block[Index[a]].size();i++){
		if(block[Index[a]][i]==a)
			F=i;
	}
	for(int i=end;i>=F;i--){
		temp.push_back(block[Index[a]][i]);
		block[Index[a]].pop_back();
	}
	end=temp.size()-1;
	for(int i=end;i>=0;i--){
		Index[temp[i]]=Index[b];
		block[Index[b]].push_back(temp[i]);
		temp.pop_back();
	}
} 
//move onto 
void move_onto(int a,int b){
	Clear(a);
	Clear(b);
	block[Index[a]].pop_back();     //move a 
	block[Index[b]].push_back(a);
	Index[a]=Index[b];	 
}
//move over 
void move_over(int a,int b){
	Clear(a);
	block[Index[a]].pop_back();     //move a 
	block[Index[b]].push_back(a);
	Index[a]=Index[b];	 
}
int main(){
	int N,a,b;
	string I1,I2;
	while(cin>>N){
		for(int i=0;i<N;i++){
			block[i].push_back(i);
			Index[i]=i;
		}
		while(cin>>I1){
			if(strcmp(I1.c_str(),"quit")==0)
				break;
			else{
				cin>>a>>I2>>b;
				if(a==b||Index[a]==Index[b]&&a<N&&b<N){
				}
				else{
					 
					if(strcmp(I1.c_str(),"move")==0&&strcmp(I2.c_str(),"onto")==0) 
						move_onto(a,b);
					else if(strcmp(I1.c_str(),"move")==0&&strcmp(I2.c_str(),"over")==0)
						move_over(a,b);
					else if(strcmp(I1.c_str(),"pile")==0&&strcmp(I2.c_str(),"onto")==0){
						Clear(b);
						Move(a,b);
					}
					else if(strcmp(I1.c_str(),"pile")==0&&strcmp(I2.c_str(),"over")==0)
						Move(a,b);	
					
				}
			}
			//print(N);
			//cout<<endl;
		}
		print(N);
		cout<<endl;
		//clear vector
		for(int i=0;i<N;i++)
			block[i].clear();
	}
	return 0;
} 

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 - The Blocks Problem-wrong answer

Post by brianfry713 » Wed Aug 21, 2013 9:18 pm

There is only one test case, only read N once and stop after reading quit. Don't print a blank line at the end of the output.
Check input and AC output for thousands of problems on uDebug!

dennisorz
New poster
Posts: 9
Joined: Wed Aug 14, 2013 6:04 pm

Re: 101 - The Blocks Problem-wrong answer

Post by dennisorz » Thu Aug 22, 2013 3:33 pm

accepted!thank you,"brianfry713".

Faisal
New poster
Posts: 3
Joined: Fri Sep 06, 2013 4:42 pm

101 the block problem , in C Runtime Error

Post by Faisal » Fri Sep 06, 2013 4:53 pm

pls help me .i trying too much to solve this problem . i dont know what is case of RE.
here is my code

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include<string.h>



#define TRUE 1
#define FALSE 0



int a[30][30];
int isValid(int x, int y,int block_length);
void move(int sou_i,int sou_j,int des_i,int des_j);
void clear(int num,int index_x,int index_y);
void Index(int num,int length,int *p_X,int *p_Y);
void move_onto(int source,int destination,int block_length);
void move_over(int source,int destination,int block_length);
void pile_onto(int source,int destination,int block_length);
void pile_over(int source,int destination,int block_length);





int main()
{
    char cmd_1[10];
        char cmd_2[10];
        int sou,des;
        int n;
        int  i,j;

        scanf("%d",&n);

        for(i=0;i<n;i++){

             a[i][0]=i;
             a[i][1]=-1;
          }

                while(1){
                    scanf("%s",cmd_1);
                    if(strcmp(cmd_1,"quit")==0) break;

                        scanf("%d%s%d",&sou,cmd_2,&des);
                        if(!(isValid(sou,des,n)))
                            continue;

                        else if(!strcmp(cmd_1,"move")&&!strcmp(cmd_2,"onto"))
                                    move_onto(sou,des,n);
                            else if(!strcmp(cmd_1,"move")&&!strcmp(cmd_2,"over"))
                                    move_over(sou,des,n);
                            else if(!strcmp(cmd_1,"pile")&&!strcmp(cmd_2,"onto"))
                                    pile_onto(sou,des,n);
                            else if(!strcmp(cmd_1,"pile")&&!strcmp(cmd_2,"over"))
                                    pile_over(sou,des,n);


                }


                for( i=0;i<n;i++){
                                printf("%d:",i);
                                for( j=0;a[i][j]!=-1;j++){
                                printf("%d ",a[i][j]);

                                }
                        printf("\n");

                }


        return 0;

}



void clear(int num,int index_x,int index_y){

    int i;
    for(i=index_y+1;a[index_x][i]!=-1;i++){
       a[a[index_x][i]][0] =a[index_x][i];
       a[a[index_x][i]][1]=-1;
    }

}
/****************************************************/
void move_onto(int source,int destination,int block_length){


        int sou_X,sou_Y;
        int des_X,des_Y;
        Index(source,block_length,&sou_X,&sou_Y);
        Index(destination,block_length,&des_X,&des_Y);
        clear(source,sou_X,sou_Y);
        clear(destination,des_X,des_Y);
        a[des_X][des_Y+1]=source;
        a[des_X][des_Y+2]=-1;
        a[sou_X][sou_Y]=-1;

}

void move_over(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);
         clear(source,sou_X,sou_Y);

        while(a[des_X][des_Y]!=-1)
                des_Y++;

        a[des_X][des_Y]=source;
        a[des_X][des_Y+1]=-1;
        a[sou_X][sou_Y]=-1;

}
void pile_onto(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);

          clear(destination,des_X,des_Y);
        move(sou_X,sou_Y,des_X,des_Y);



}

void pile_over(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);
         move(sou_X,sou_Y,des_X,des_Y);



}
void move(int sou_i,int sou_j,int des_i,int des_j){
    int i;
     while(a[des_i][des_j]!=-1)
                ++des_j;

        for( i=sou_j;a[sou_i][i]!=-1;i++){
                a[des_i][des_j]=a[sou_i][i];
                ++des_j;

        }


        a[des_i][des_j]=-1;
        a[sou_i][sou_j]=-1;
}

void Index(int num,int length,int *p_X,int *p_Y){


    int i=0;    /*it count for x position*/
    int j;      /*it count for y position*/
    while(i<length){
        j=0;
        while(a[i][j]!=-1){
            if(num==a[i][j]){
                *p_X=i;
                *p_Y=j;
                break;
                }
            j++;
        }
        i++;

    }

}
int isValid(int x, int y,int block_length){
        int i,j,k;
        if(x==y)
                        return FALSE;

                for( i=0;i<block_length;i++){
                        for( j=0;a[i][j]!=-1;j++)
                                if(x==a[i][j]){
                                        for( k=0;a[i][k]!=-1;k++)
                                                if(y==a[i][k])
                                                        return FALSE;
                                }


                }
                return TRUE;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 the block problem , in C Runtime Error

Post by brianfry713 » Fri Sep 06, 2013 10:41 pm

Try the I/O I posted at http://online-judge.uva.es/board/viewtopic.php?t=71285
On my machine your code is throwing this:
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400bf6 in move (sou_i=25, sou_j=0, des_i=13, des_j=1030)
at code.c:151
151 for( i=sou_j;a[sou_i]!=-1;i++){
Check input and AC output for thousands of problems on uDebug!

Faisal
New poster
Posts: 3
Joined: Fri Sep 06, 2013 4:42 pm

Re: 101 the block problem , in C Runtime Error

Post by Faisal » Sat Sep 14, 2013 6:59 pm

should add new condition for destination index ...& can any what the reason for segmentation error

Faisal
New poster
Posts: 3
Joined: Fri Sep 06, 2013 4:42 pm

Re: 101 the block problem , in C Runtime Error

Post by Faisal » Sat Sep 14, 2013 11:22 pm

I edit my code but still have same problem

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include<string.h>



#define TRUE 1
#define FALSE 0



int a[100][100];
int isValid(int x, int y,int block_length);
void move(int sou_i,int sou_j,int des_i,int des_j);
void clear(int num,int index_x,int index_y);
void Index(int num,int length,int *p_X,int *p_Y);
void move_onto(int source,int destination,int block_length);
void move_over(int source,int destination,int block_length);
void pile_onto(int source,int destination,int block_length);
void pile_over(int source,int destination,int block_length);





int main()
{
    char cmd_1[10];
        char cmd_2[10];
        int sou,des;
        int n;
        int  i,j;

        scanf("%d",&n);

        for(i=0;i<n;i++){

             a[i][0]=i;
             a[i][1]=-1;
          }

                while(1){
                    scanf("%s",cmd_1);
                    if(strcmp(cmd_1,"quit")==0) break;

                        scanf("%d%s%d",&sou,cmd_2,&des);
                        if((!(isValid(sou,des,n)))||sou>n||des>n)
                            continue;

                        else if(!strcmp(cmd_1,"move")&&!strcmp(cmd_2,"onto"))
                                    move_onto(sou,des,n);
                            else if(!strcmp(cmd_1,"move")&&!strcmp(cmd_2,"over"))
                                    move_over(sou,des,n);
                            else if(!strcmp(cmd_1,"pile")&&!strcmp(cmd_2,"onto"))
                                    pile_onto(sou,des,n);
                            else if(!strcmp(cmd_1,"pile")&&!strcmp(cmd_2,"over"))
                                    pile_over(sou,des,n);


                }


                for( i=0;i<n;i++){
                                printf("%d:",i);
                                for( j=0;a[i][j]!=-1;j++){
                                printf("%d ",a[i][j]);

                                }
                        printf("\n");

                }


        return 0;

}



void clear(int num,int index_x,int index_y){

    int i;
    for(i=index_y+1;a[index_x][i]!=-1;i++){
       a[a[index_x][i]][0] =a[index_x][i];
       a[a[index_x][i]][1]=-1;
    }

}
/****************************************************/
void move_onto(int source,int destination,int block_length){


        int sou_X,sou_Y;
        int des_X,des_Y;
        sou_X=sou_Y=des_X=des_Y=0;
        Index(source,block_length,&sou_X,&sou_Y);
        Index(destination,block_length,&des_X,&des_Y);
        clear(source,sou_X,sou_Y);
        clear(destination,des_X,des_Y);
        a[des_X][des_Y+1]=source;
        a[des_X][des_Y+2]=-1;
        a[sou_X][sou_Y]=-1;

}

void move_over(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
        sou_X=sou_Y=des_X=des_Y=0;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);
         clear(source,sou_X,sou_Y);

        while(a[des_X][des_Y]!=-1)
                des_Y++;

        a[des_X][des_Y]=source;
        a[des_X][des_Y+1]=-1;
        a[sou_X][sou_Y]=-1;

}
void pile_onto(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
        sou_X=sou_Y=des_X=des_Y=0;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);

        clear(destination,des_X,des_Y);
        move(sou_X,sou_Y,des_X,des_Y);



}

void pile_over(int source,int destination,int block_length){

        int sou_X,sou_Y;
        int des_X,des_Y;
        sou_X=sou_Y=des_X=des_Y=0;
         Index(source,block_length,&sou_X,&sou_Y);
         Index(destination,block_length,&des_X,&des_Y);
         move(sou_X,sou_Y,des_X,des_Y);



}
void move(int sou_i,int sou_j,int des_i,int des_j){
    int i;
     while(a[des_i][des_j]!=-1){
                des_j++;
     }

         i=sou_j;
        while(a[sou_i][i]!=-1){
              a[des_i][des_j]=a[sou_i][i];
              des_j++;
              i++;
        }


        a[des_i][des_j]=-1;
        a[sou_i][sou_j]=-1;
}

void Index(int num,int length,int *p_X,int *p_Y){


    int i=0;    /*it count for x position*/
    int j;      /*it count for y position*/
    while(i<length){
        j=0;
        while(a[i][j]!=-1){
            if(num==a[i][j]){
                *p_X=i;
                *p_Y=j;
                break;
                }
            j++;
        }
        i++;

    }

}
int isValid(int x, int y,int block_length){
        int i,j,k;
        if(x==y)
                        return FALSE;

                for( i=0;i<block_length;i++){
                        for( j=0;a[i][j]!=-1;j++)
                                if(x==a[i][j]){
                                        for( k=0;a[i][k]!=-1;k++)
                                                if(y==a[i][k])
                                                        return FALSE;
                                }


                }


                return TRUE;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 the block problem , in C Runtime Error

Post by brianfry713 » Sun Sep 15, 2013 5:10 am

I use gcc. Your code is still throwing a seg fault on my input. See:http://ideone.com/dks3lr
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400bfa in move (sou_i=0, sou_j=0, des_i=0, des_j=10008)
line 158: a[des_i][des_j]=a[sou_i];
Check input and AC output for thousands of problems on uDebug!

wuhao
New poster
Posts: 2
Joined: Fri Oct 25, 2013 3:24 pm

101 The Block Problem Wrong Answer

Post by wuhao » Fri Oct 25, 2013 3:44 pm

Excuse me,need for help. I've done a lot of test, I think the code is right. but I got WA. Anyone can help me!

Code: Select all

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

typedef struct COMMAND{
	int m_iCmd;
	int m_iA;
	int m_iB;
}COMMAND;

int giNowBlock[25],giNextBlock[25],giPriorBlock[25];
COMMAND gCmd;

inline int ParseCommand(const char * szCmd)
{
	int i;
	if('m'==szCmd[0])
		gCmd.m_iCmd=0;
	else
		if('p'==szCmd[0])
			gCmd.m_iCmd=2;
		else
			return 0;

	gCmd.m_iA=0;
	gCmd.m_iB=0;
	for(i=5;szCmd[i]<='9'&&szCmd[i]>='0';++i)
		gCmd.m_iA=10*gCmd.m_iA+szCmd[i]-'0';
	i+=2;

	gCmd.m_iCmd+=('n'==szCmd[i])?0:1;
	for(i+=4;szCmd[i]<='9'&&szCmd[i]>='0';++i)
		gCmd.m_iB=10*gCmd.m_iB+szCmd[i]-'0';

	return 1;
}
inline void MoveOnto(int iA,int iB)
{
	int iTemp1=iA;
	int iTemp2=giNextBlock[iTemp1];
	while(iTemp1!=iTemp2)
	{
		iTemp1=iTemp2;
		iTemp2=giNextBlock[iTemp1];
		giNowBlock[iTemp1]=iTemp1;
		giNextBlock[iTemp1]=iTemp1;
		giPriorBlock[iTemp1]=iTemp1;
	}

	iTemp1=iB;
	iTemp2=giNextBlock[iTemp1];
        while(iTemp1!=iTemp2)
        {
                iTemp1=iTemp2;
                iTemp2=giNextBlock[iTemp1];
                giNowBlock[iTemp1]=iTemp1;
                giNextBlock[iTemp1]=iTemp1;
		giPriorBlock[iTemp1]=iTemp1;
	}

	int iPior=giPriorBlock[iA];
	if(iPior!=iA)
        	giNextBlock[iPior]=iPior;

	giNowBlock[iA]=giNowBlock[iB];
	giNextBlock[iA]=iA;
	giPriorBlock[iA]=iB;
	giNextBlock[iB]=iA;
}
inline void MoveOver(int iA,int iB)
{
	int iTemp1=iB;
	while(iTemp1!=giNextBlock[iTemp1])
	iTemp1=giNextBlock[iTemp1];
	int iTemp2=iA;
    int iTemp3=giNextBlock[iTemp2];
    while(iTemp2!=iTemp3)
    {
        iTemp2=iTemp3;
        iTemp3=giNextBlock[iTemp2];
        giNowBlock[iTemp2]=iTemp2;
        giNextBlock[iTemp2]=iTemp2;
		giPriorBlock[iTemp2]=iTemp2;
    }

	int iPior=giPriorBlock[iA];
	if(iPior!=iA)
		giNextBlock[iPior]=iPior;

	giNowBlock[iA]=giNowBlock[iTemp1];
    giNextBlock[iA]=iA;
	giPriorBlock[iA]=iTemp1;
    giNextBlock[iTemp1]=iA;
}
inline void PileOnto(int iA,int iB)
{
	int iTemp1=iB;
    int iTemp7=giNextBlock[iTemp1];
    while(iTemp1!=iTemp7)
    {
        iTemp1=iTemp7;
        iTemp7=giNextBlock[iTemp1];
        giNowBlock[iTemp1]=iTemp1;
        giNextBlock[iTemp1]=iTemp1;
		giPriorBlock[iTemp1]=iTemp1;
    }

	int iPior=giPriorBlock[iA];
	if(iPior!=iA)
        	giNextBlock[iPior]=iPior;

	giNextBlock[iB]=iA;
        giPriorBlock[iA]=iB;

	iTemp1=giNowBlock[iB];
	iTemp7=giNextBlock[iA];
	for(int iTemp=iA;iTemp!=iTemp7;)
        {
                giNowBlock[iTemp]=iTemp1;
		iTemp=iTemp7;
		iTemp7=giNextBlock[iTemp];
        }
	giNowBlock[iTemp7]=iTemp1;
}
inline void PileOver(int iA,int iB)
{
	int iTemp1=iB;
    while(iTemp1!=giNextBlock[iTemp1])
        iTemp1=giNextBlock[iTemp1];

	int iPior=giPriorBlock[iA];
	if(iPior!=iA)
		giNextBlock[iPior]=iPior;

	giNextBlock[iTemp1]=iA;
	giPriorBlock[iA]=iTemp1;

	int iTemp2=giNextBlock[iA];
	int iTemp3=giNowBlock[iB];
	for(int iTemp=iA;iTemp!=iTemp2;)
	{
		giNowBlock[iTemp]=iTemp3;
		iTemp=iTemp2;
		iTemp2=giNextBlock[iTemp2];
	}
	giNowBlock[iTemp2]=iTemp3;
}

int main()
{
	int iNum=0;
	cin>>iNum;
	for(int i=0;i<iNum;++i)
	{
		giNowBlock[i]=i;
		giNextBlock[i]=i;
		giPriorBlock[i]=i;
	}

	string str;
	cin.ignore();
	while(true)
	{
		getline(cin,str);
		if(ParseCommand(str.c_str())==1)
		{
			if(giNowBlock[gCmd.m_iA]==giNowBlock[gCmd.m_iB])
				continue;
			switch(gCmd.m_iCmd)
			{
				case 0:
					MoveOnto(gCmd.m_iA,gCmd.m_iB);
					break;
				case 1:
					MoveOver(gCmd.m_iA,gCmd.m_iB);
					break;
				case 2:
					PileOnto(gCmd.m_iA,gCmd.m_iB);
					break;
				case 3:
					PileOver(gCmd.m_iA,gCmd.m_iB);
			}
		}
		else break;
	}

	int iOut;
	for(int i=0;i<iNum;++i)
	{
		cout<<i<<":";
		if(giNowBlock[i]==i)
		{
			for(iOut=i;iOut!=giNextBlock[iOut];iOut=giNextBlock[iOut])
				cout<<' '<<iOut;
			cout<<' '<<iOut;
		}
		cout<<endl;
	}

	return 1;
}
Sorry for my repetitive code..Thanks.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 101 The Block Problem Wrong Answer

Post by brianfry713 » Fri Oct 25, 2013 9:35 pm

Change the line line return 1; to return 0;
Check input and AC output for thousands of problems on uDebug!

wuhao
New poster
Posts: 2
Joined: Fri Oct 25, 2013 3:24 pm

Re: 101 The Block Problem Wrong Answer

Post by wuhao » Sat Oct 26, 2013 6:01 am

brianfry713 wrote:Change the line line return 1; to return 0;
Thanks. It‘s really accepted.

Post Reply

Return to “Volume 1 (100-199)”