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

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu »

Thanks a lot! I finally work it out! I think my pile_onto()function has some small mistakes.

Tony1223
New poster
Posts: 1
Joined: Wed Feb 09, 2005 4:58 pm

#101 [java]

Post by Tony1223 »

I can run the example correctly,
but I cant not pass the example.

I wonder where I am wrong. >_<


btw, the online-judge is really not familiar with java users.........+_+

/* @JUDGE_ID: 57168ET 101 JAVA ""*/


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

class Main{


static String[] block=new String[1];

public static void main(String args[]) throws IOException{

String inputStr=ReadLn(255);
//BufferedReader input = new BufferedReader(new FileReader(new File("command.txt")));
//String inputStr=input.readLine();
//System.out.println(inputStr);

StringTokenizer idata=new StringTokenizer (inputStr);

int n=Integer.parseInt(idata.nextToken());

block=new String[n];

for(int i=0;i<n;i++){
block=""+i;
}


for(int i=0;i<n;i++){
block=" "+i;
}

while(true){

inputStr=ReadLn(255);
//inputStr=input.readLine();
//System.out.println(inputStr);

idata = new StringTokenizer (inputStr);

String command=idata.nextToken();

int control=-1;
int control2=-1;

if(command.indexOf("quit")!=-1) break;
else if(command.indexOf("move")!=-1) control=1;
else if(command.indexOf("pile")!=-1) control=2;

int a=Integer.parseInt(idata.nextToken());

command=idata.nextToken();

if(command.indexOf("onto")!=-1)control2=1;
else if(command.indexOf("over")!=-1) control2=2;

int b=Integer.parseInt(idata.nextToken());

if(a==b) continue;

for(int i=0;i<n;i++){
if(block.indexOf(""+a)!=-1&&block.indexOf(""+b)!=-1) continue;
}


if(control==1&&control2==1){ // move a onto b
moveAontoB(a,b);
}else if(control==1&&control2==2){ //move a over b
moveAoverB(a,b);
}else if(control==2&&control2==1){// pile a onto b
pileAontoB(a,b);
}else if(control==2&&control2==2){// pile a over b
pileAoverB(a,b);
}

}

for(int i=0;i<n;i++){
if(i<10) System.out.println(" "+i+":"+block);
else System.out.println(i+":"+block);
}


}

static void moveAontoB(int a,int b){

int ALocation= -1;

for(int i=0;i<block.length;i++){
if(block.indexOf(""+a)!=-1) ALocation=i;
}

int BLocation= -1;
for(int i=0;i<block.length;i++){
if(block.indexOf(""+b)!=-1) BLocation=i;
}

String temp=block[ALocation].substring(block[ALocation].indexOf(" "+a));
block[ALocation]=block[ALocation].substring(0,block[ALocation].indexOf(" "+a));

String temp3="";

if(temp.indexOf(a+" ")!=-1){
if(a<10)
temp3=temp.substring(temp.indexOf(" "+a)+2);
else
temp3=temp.substring(temp.indexOf(" "+a)+3);

temp=temp.substring(0,temp.indexOf(temp3));
}



String temp2="";

if(block[BLocation].indexOf(b+" ")!=-1){//表示b後面有加數字

if(b<10)
temp2=block[BLocation].substring(block[BLocation].indexOf(" "+b)+2);
else
temp2=block[BLocation].substring(block[BLocation].indexOf(" "+b)+3);

block[BLocation]=block[BLocation].substring(0,block[BLocation].indexOf(temp2))+temp;
}else{
block[BLocation]=block[BLocation]+temp;
}

StringTokenizer idata = new StringTokenizer (temp2);

while(idata.hasMoreTokens()){

int k=Integer.parseInt(idata.nextToken());
block[k]=block[k]+ " "+k;
}

idata = new StringTokenizer (temp3);

while(idata.hasMoreTokens()){

int k=Integer.parseInt(idata.nextToken());
block[k]=block[k]+ " "+k;
}


}
static void moveAoverB(int a,int b){

int ALocation= -1;

for(int i=0;i<block.length;i++){
if(block.indexOf(""+a)!=-1) ALocation=i;
}

int BLocation= -1;

for(int i=0;i<block.length;i++){
if(block.indexOf(""+b)!=-1) BLocation=i;
}

String temp=block[ALocation].substring(block[ALocation].indexOf(" "+a));
block[ALocation]=block[ALocation].substring(0,block[ALocation].indexOf(" "+a));

String temp3="";

if(temp.indexOf(a+" ")!=-1){
if(a<10)
temp3=temp.substring(temp.indexOf(" "+a)+2);
else
temp3=temp.substring(temp.indexOf(" "+a)+3);

temp=temp.substring(0,temp.indexOf(temp3));
}


block[BLocation]=block[BLocation]+temp;

StringTokenizer idata = new StringTokenizer (temp3);

while(idata.hasMoreTokens()){

int k=Integer.parseInt(idata.nextToken());
block[k]=block[k]+ " "+k;
}

}

static void pileAoverB(int a,int b){
int ALocation= -1;

for(int i=0;i<block.length;i++){
if(block[i].indexOf(""+a)!=-1) ALocation=i;
}

int BLocation= -1;

for(int i=0;i<block.length;i++){
if(block[i].indexOf(""+b)!=-1) BLocation=i;
}

String temp=block[ALocation].substring(block[ALocation].indexOf(" "+a));
block[ALocation]=block[ALocation].substring(0,block[ALocation].indexOf(" "+a));



block[BLocation]=block[BLocation]+temp;
}

static void pileAontoB(int a,int b){

int ALocation= -1;

for(int i=0;i<block.length;i++){
if(block[i].indexOf(""+a)!=-1) ALocation=i;
}

int BLocation= -1;
for(int i=0;i<block.length;i++){
if(block[i].indexOf(""+b)!=-1) BLocation=i;
}

String temp=block[ALocation].substring(block[ALocation].indexOf(" "+a));
block[ALocation]=block[ALocation].substring(0,block[ALocation].indexOf(" "+a));

String temp2="";

if(block[BLocation].indexOf(b+" ")!=-1){//表示b後面有加數字

if(b<10)
temp2=block[BLocation].substring(block[BLocation].indexOf(" "+b)+2);
else
temp2=block[BLocation].substring(block[BLocation].indexOf(" "+b)+3);

block[BLocation]=block[BLocation].substring(0,block[BLocation].indexOf(temp2))+temp;
}else{
block[BLocation]=block[BLocation]+temp;
}

StringTokenizer idata = new StringTokenizer (temp2);

while(idata.hasMoreTokens()){

int k=Integer.parseInt(idata.nextToken());
block[k]=block[k]+ " "+k;
}

}


static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}


}
//"@end_of_source_code

Cruzer
New poster
Posts: 11
Joined: Thu Feb 10, 2005 4:18 am
Location: Waterloo, ON, Canada

101 RE, please help

Post by Cruzer »

I've tested many different inputs(including the ones in the other posts on thsi board) and can't find the problem. I've double checked all my loops and they seem to be fine. This error is really stumping me. Here is my code:

Code: Select all

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

#define MAX_STACKS 25

/* Function Prototypes */
void initBlockWorld( int stacks[MAX_STACKS][MAX_STACKS], int numStacks );
int findBlock( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target );
void printBlockWorld( int stacks[MAX_STACKS][MAX_STACKS], int numStacks );
void returnBlocksOnTop( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target, int targetStack );
void pileBlocks( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target, int src, int dest );

main() {
    int stacks[MAX_STACKS][MAX_STACKS];   /* Stacks of blocks. Blocks represented by integers, non-blocks by -1 */
    int numStacks;        /* Number of stacks, number of blocks is the same */
    char command[25];     /* Command to robot (move/pile, onto/over) */
    int srcBlock, destBlock;    /* Block to move/pile, onto/over */
    int srcStack, destStack;    /* Stack of the src/dest blocks */
    char cmd1[6], cmd2[6];      /* cmd1 = move/pile, cmd2 = onto/over */
    char temp[6];
    
    /* Get number of stacks and initialize the block world */
    scanf("%d", &numStacks);
    initBlockWorld( stacks, numStacks );
    
    /* Get first command */
    fflush(stdin);
    gets(command);
    
    /* Execute all commands from input until "quit" is input */
    while( strcmp(command, "quit") != 0 ) {
        /* Extract tokens from command string */
        strcpy( cmd1, strtok( command, " " ) );
        strcpy( temp, strtok( NULL, " " ) );
        sscanf( temp, "%d", &srcBlock );
        strcpy( cmd2, strtok( NULL, " " ) );
        strcpy( temp, strtok( NULL, "\n" ) );
        sscanf( temp, "%d", &destBlock );
    
        /* Find stack of the source and destination blocks */
        srcStack = findBlock( stacks, numStacks, srcBlock );
        destStack = findBlock( stacks, numStacks, destBlock );
        
        /* Make sure srcStack isn't the same as destStack, if it is then ignore command */
        if( srcStack != destStack ) {
            /* If cmd1 is move, return blocks on top of source block to original stacks */
            if( strcmp( cmd1, "move" ) == 0 ) {
                returnBlocksOnTop( stacks, numStacks, srcBlock, srcStack );
            }
        
            /* If cmd2 is onto, return blocks on top of dest block to original stacks */
            if( strcmp( cmd2, "onto" ) == 0 ) {
                returnBlocksOnTop( stacks, numStacks, destBlock, destStack );
            }
            
            /* Pile from src to dest */
            pileBlocks( stacks, numStacks, srcBlock, srcStack, destStack );
        }
    
        /* Get next command */
        fflush(stdin);
        gets(command);
    }

    /* Print block world */
    printBlockWorld( stacks, numStacks );
}

void initBlockWorld( int stacks[MAX_STACKS][MAX_STACKS], int numStacks ) {
    int i, j;
    
    /* Set all entries to -1 */
    for( i = 0; i < numStacks; i++ ) {
        for( j = 0; j < numStacks; j++ ) {
            stacks[i][j] = -1;
        }
    }
    
    /* Place initial blocks */
    for( i = 0; i < numStacks; i++ ) {
        stacks[i][0] = i;
    }
}

/* Returns which stack the target block is in */
int findBlock( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target ) {
    int i, j;
    
    for( i = 0; i < numStacks; i++ ) {
        for( j = 0; j < numStacks; j++ ) {
            if( target == stacks[i][j] ) {
                return i;
            }
        }
    }
}

void printBlockWorld( int stacks[MAX_STACKS][MAX_STACKS], int numStacks ) {
    int i, j;
    
    /* Print stack#: block1, block2, etc... */
    for( i = 0; i < numStacks; i++ ) {
        printf("%d:", i);
        for( j = 0; j < numStacks; j++ ) {
            if( stacks[i][j] != -1 ) {
                printf(" %d", stacks[i][j]);
            }
        }
        if( i < numStacks-1 ) {
            printf("\n");
        }
    }
}

/* Returns all blocks on top of target block back to orginal stack. Returns the location of the target block in its stack */
void returnBlocksOnTop( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target, int targetStack ) {
    int i, loc;
    
    /* Find location of target block within stack */
    for( i = 0; i < numStacks; i++ ) {
        if( stacks[targetStack][i] == target ) {
            loc = i;
        }
    }
    
    /* Clear blocks off the top of target */
    /* Start from top of stack, work way down to target. Use pile to put the block onto its original stack */
    for( i = numStacks-1; i > loc; i-- ) {
        if( stacks[targetStack][i] != -1 ) {
            pileBlocks( stacks, numStacks, stacks[targetStack][i], targetStack, stacks[targetStack][i] );
        }
    }
}

/* Piles all blocks starting with target block in source stack to destination stack */
void pileBlocks( int stacks[MAX_STACKS][MAX_STACKS], int numStacks, int target, int src, int dest ) {
    int i, srcLoc, destLoc;
    
    if( src != dest ) {
        /* Get srcLoc, destLoc - the locations to start swapping */
        for( i = 0; i < numStacks; i++ ) {
            if( stacks[src][i] == target ) {
                srcLoc = i;
                break;
            }
        }
        for( i = 0; i < numStacks; i++ ) {
            if( stacks[dest][i] == -1 ) {
                destLoc = i;
                break;
            }
        }
        
        /* Swap all blocks from src stack with non-blocks (-1) from dest stack starting at the srcLoc and destLoc */
        while( stacks[src][srcLoc] != -1 && srcLoc < numStacks ) {
            stacks[dest][destLoc] = stacks[src][srcLoc];
            stacks[src][srcLoc] = -1;
            srcLoc++;
            destLoc++;
        }    
    }
    else {
        /* Error! Can't have src == dest */
    }
}

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Problem 101 The Blocks Problem

Post by ibrahim »

Please tell me what's the wrong with my code.

Code: Select all

#include<stdio.h>
#include<string.h>
int block_number;
int pos;

struct b
{
	int top;
	int stack[26];
}block[26];

void init()
{
	int i;
	for(i=0;i<=block_number;i++)
	{
		block[i].top = 0;
		block[i].stack[0]=i;
	}
}

int search(int number)
{
	int i;
	for(i=0;i<block_number;i++)
	{
		for(pos=0;pos<=block[i].top;pos++)
			if(block[i].stack[pos] == number)
				return i;
	}
	return 0;
}

int check(int a, int b)
{
	int a_stack, b_stack;
	a_stack=search(a);
	b_stack=search(b);
	if(a_stack==b_stack)
		return 0;
return 1;
}


int pop(int stack_number)
{
	int tmp;

	tmp= block[stack_number].stack[block[stack_number].top];
	block[stack_number].top--;
	return tmp;
}



void push(int stack_number, int number)
{
	block[stack_number].top ++;
	block[stack_number].stack[block[stack_number].top]=number;
}

void release(int stack_number, int item)
{
	int tmp,i;
	for(i=block[stack_number].top;;i--)
	{
			tmp=pop(stack_number);
			if(tmp==item)
			{
				block[stack_number].top++;
				break;
			}
			push(tmp,tmp);
			block[stack_number].top--;
			

	}
}

void move_onto(int a, int b)
{
	int a_stack,b_stack;
	a_stack=search(a);
	release(a_stack,a);
	b_stack=search(b);
	release(b_stack,b);
	
	push(b_stack,pop(a_stack));
}

void move_over(int a, int b)
{
	int a_stack, b_stack;
	a_stack=search(a);
	release(a_stack,a);
	b_stack=search(b);
	
	push(b_stack,pop(a_stack));
}
	
void pile_onto(int a, int b)
{
	int a_stack, b_stack;
	int a_pos,i;
	a_stack=search(a);
	a_pos=pos;
	b_stack=search(b);
	release(b_stack,b);
	
	push(b_stack,a);
	for(i=a_pos;i<=block[a_stack].top;i++)
	{
		block[b_stack].stack[block[b_stack].top++ ]=block[a_stack].stack[i];
	}
	block[a_stack].top = a_pos-1;
	block[b_stack].top--;
}



void pile_over(int a, int b)
{
	int a_stack, b_stack;
	int a_pos,i;
	a_stack=search(a);
	a_pos=pos;
	b_stack=search(b);
	push(b_stack,a);
	for(i=a_pos;i<=block[a_stack].top;i++)
	{
		block[b_stack].stack[block[b_stack].top++ ]=block[a_stack].stack[i];
	}
	block[a_stack].top = a_pos-1;
	block[b_stack].top--;
}



int main()
{
	char string[50],option[50];
	int a,b,i,j;
	
	scanf("%d",&block_number);
	init();		
	while(1)
	{
		scanf("%s", string);
		if(strcmp(string,"quit")==0)
			break;
		scanf("%d %s %d",&a,option,&b);
		if(check(a,b)==1)
		{
			if(strcmp(string,"move")==0 && strcmp(option,"onto")==0)
			{
				move_onto(a,b);
			}
			else if(strcmp(string,"move")==0 && strcmp(option,"over")==0)
			{
				move_over(a,b);
			}
			else if(strcmp(string,"pile")==0 && strcmp(option,"onto")==0)
			{
				pile_onto(a,b);
			}
			else if(strcmp(string,"pile")==0 && strcmp(option,"over")==0)
			{
				pile_over(a,b);
			}
		}
	}
	for(i=0;i<block_number;i++)
	{
		printf("%d: ",i);
		for(j=0;j<=block[i].top;j++)
			printf("%d ",block[i].stack[j]);
		printf("\n");
	}
	


return 0;
}

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

Post by Ghust_omega »

Hi !! ibrahim here I put some I/O, 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 !!

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim »

Thanks Omega i got accept. I made a very littel mistake.

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim »

Please try this input.

Code: Select all

19 
move 1 onto 0 
move 0 onto 1 
move 0 onto 2 
move 2 onto 1 
move 4 over 5 
move 7 onto 8 
move 9 onto 7 
move 7 over 9 
move 9 over 7 
move 11 over 10 
move 12 over 10 
move 13 over 10 
move 14 over 10 
move 16 over 15 
move 17 over 15 
move 18 over 15 
move 16 onto 14 
pile 17 onto 12 
move 15 over 10 
pile 17 onto 14 
pile 15 over 7 
pile 6 over 5 
pile 3 onto 9 
quit 

Cruzer
New poster
Posts: 11
Joined: Thu Feb 10, 2005 4:18 am
Location: Waterloo, ON, Canada

Post by Cruzer »

This input works.. it produces the following:
0: 0
1: 1 2
2:
3:
4:
5: 5 4 6
6:
7:
8: 8 7 9 3
9:
10: 10 11 12
11:
12:
13: 13
14: 14 17
15: 15
16: 16
17:
18: 18

This is correct is it not?

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

Post by Ghust_omega »

Hi !! Cruzer the ouput is fine the RE I think is because the process of read the input because
I run your code in my machine (linux) and gives to me segmentation fault when I just put the first number ....
Hope it helps
Keep posting !!

Cruzer
New poster
Posts: 11
Joined: Thu Feb 10, 2005 4:18 am
Location: Waterloo, ON, Canada

Post by Cruzer »

Thanks I found the problem. Apparently fflush() doesn't work on the judge or in Unix or something. Fixed now.

blank3
New poster
Posts: 3
Joined: Mon Dec 13, 2004 12:05 am

#101 WA

Post by blank3 »

Hi ppl, i seem not to understand this problem correctly. I can't produce the following output from the input below. Can some one point me what am i doing wrong... i'd be grateful!

Code: Select all

Code:

19
move 1 onto 0
move 0 onto 1
move 0 onto 2
move 2 onto 1
move 4 over 5
move 7 onto 8
move 9 onto 7
move 7 over 9
move 9 over 7
move 11 over 10
move 12 over 10
move 13 over 10
move 14 over 10
move 16 over 15
move 17 over 15
move 18 over 15
move 16 onto 14
pile 17 onto 12
move 15 over 10
pile 17 onto 14
pile 15 over 7
pile 6 over 5
pile 3 onto 9
quit


Ouput:
Code:

0:0
1:1 2
2:
3:
4:
5:5 4 6
6:
7:
8:8 7 9 3
9:
10:10 11 12
11:
12:
13:13
14:14 17
15:15
16:16
17:
18:18 

Code: Select all

#include <iostream>
#include <string>

using namespace std;

int WS= 0;			//worldsize
short int BW[25][25];		//blockworld
short int BL[25][2];		//blockworld
string P1, P2;			//parameter 1, parameter 2
int A, B;			//block A, block B
const int X= 0, Y= 1;

void robotArm(string P1, int A, string P2, int B);
void printWorld();
void initializeWorld();
bool anyBlocksAbove(int A);
void moveBlock(int A, int x, int y);
void moveBlocksAbove(int x, int y, int DestX);
int findFreeX(int avoidX[], int Elements);
int findFreeY(int x);
int getX(int A);
int getY(int A);

int main() {
	cin >> WS;

	initializeWorld();	

	do {
		cin >> P1;
		
		if (P1 == "quit") {
			printWorld();
			break;
		} else if (P1 == "print") {
			printWorld();
		} else if (P1 == "init") {
			initializeWorld();
			printWorld();
		} else {
			cin >> A;
			cin >> P2;
			cin >> B;
			
			if (BL[A][X] != BL[B][X]) {
				robotArm(P1, A, P2, B);
				//printWorld();
			}
		}
	} while (1);
	
	return 0;
}

void robotArm(string P1, int A, string P2, int B) {
	int srcX= getX(A);
	int destX= getX(B);
	
	if (P1 == "move") {
		if (P2 == "over") {
			if (! anyBlocksAbove(A)) {
				moveBlock(A, destX, findFreeY(getX(B)));
			} else {
				int avoidX[]= { srcX, destX };
				int tmpX= findFreeX(avoidX, sizeof(avoidX)/4);
				int tmpY= findFreeY(tmpX) -1;
				
				moveBlocksAbove(srcX, getY(A), tmpX);
				moveBlock(A, destX, findFreeY(B));
				moveBlocksAbove(tmpX, tmpY, srcX);
			}
		} else {
			if (! anyBlocksAbove(A) && ! anyBlocksAbove(B)) {
				moveBlock(A, destX, findFreeY(getX(B)));
			} else if (anyBlocksAbove(A) && ! anyBlocksAbove(B)) {
				int avoidX[]= { srcX, destX };
				int tmpX= findFreeX(avoidX, sizeof(avoidX)/4);
				int tmpY= findFreeY(tmpX) -1;
				
				moveBlocksAbove(srcX, getY(A), tmpX);
				moveBlock(A, destX, findFreeY(getX(B)));
				moveBlocksAbove(tmpX, tmpY, srcX);
			} else if (! anyBlocksAbove(A) && anyBlocksAbove(B)) {
				int avoidX[]= { srcX, destX };
				int tmpX= findFreeX(avoidX, sizeof(avoidX)/4);
				int tmpY= findFreeY(tmpX) -1;
				
				moveBlocksAbove(destX, getY(B), tmpX);
				moveBlock(A, destX, findFreeY(getX(B)));
				moveBlocksAbove(tmpX, tmpY, destX);
			} else if (anyBlocksAbove(A) && anyBlocksAbove(B)) {
				//A block
				int avoidX1[]= { srcX, destX };
				int tmpX1= findFreeX(avoidX1, sizeof(avoidX1)/4);
				int tmpY1= findFreeY(tmpX1) -1;
				
				moveBlocksAbove(srcX, getY(A), tmpX1);
				//
				
				//B block
				int avoidX2[]= { srcX, destX, tmpX1 };
				int tmpX2= findFreeX(avoidX2, sizeof(avoidX2)/4);
				int tmpY2= findFreeY(tmpX2) -1;
				
				moveBlocksAbove(destX, getY(B), tmpX2);
				//
				
				moveBlock(A, destX, findFreeY(getX(B)));
				
				moveBlocksAbove(tmpX1, tmpY1, srcX);
				moveBlocksAbove(tmpX2, tmpY2, destX);
			}
		}
	} else {
		if (P2 == "over") {
			if (anyBlocksAbove(A)) {
				int avoidX[]= { srcX, destX };
				int tmpX= findFreeX(avoidX, sizeof(avoidX)/4);
				int tmpY= findFreeY(tmpX) -1;
				int destY= findFreeY(destX);				
				
				moveBlocksAbove(srcX, getY(A), tmpX);
				moveBlock(A, destX, destY);
				moveBlocksAbove(tmpX, tmpY, destX);
			} else {
				moveBlock(A, getX(B), findFreeY(getX(B)));
			}
		} else {
			if (! anyBlocksAbove(A) && ! anyBlocksAbove(B)) {
				moveBlock(A, getX(B), findFreeY(getX(B)));
			} else if (anyBlocksAbove(A) && ! anyBlocksAbove(B)) {
				int avoidX[]= { srcX, destX };
				int tmpX= findFreeX(avoidX, sizeof(avoidX)/4);
				int tmpY= findFreeY(tmpX) -1;
				int destY= findFreeY(destX);				
				
				moveBlocksAbove(srcX, getY(A), tmpX);
				moveBlock(A, destX, destY);
				moveBlocksAbove(tmpX, tmpY, destX);				
			} else if (! anyBlocksAbove(A) && anyBlocksAbove(B)) {
				int avoidX1[]= { srcX, destX };
				int tmpX1= findFreeX(avoidX1, sizeof(avoidX1)/4);
				int tmpY1= findFreeY(tmpX1) -1;
				
				moveBlocksAbove(destX, getY(B), tmpX1);
				moveBlock(A, getX(B), findFreeY(getX(B)));
				moveBlocksAbove(tmpX1, tmpY1, destX);
			} else if (anyBlocksAbove(A) && anyBlocksAbove(B)) {
				int avoidX1[]= { srcX, destX };
				int tmpX1= findFreeX(avoidX1, sizeof(avoidX1)/4);
				int tmpY1= findFreeY(tmpX1) -1;
				
				moveBlocksAbove(destX, getY(B), tmpX1);
				
				//pile A move
				int avoidX2[]= { srcX, destX, tmpX1 };
				int tmpX2= findFreeX(avoidX2, sizeof(avoidX2)/4);
				int tmpY2= findFreeY(tmpX2) -1;
				
				moveBlocksAbove(srcX, getY(A), tmpX2);
				moveBlock(A, destX, findFreeY(getX(B)));
				moveBlocksAbove(tmpX2, tmpY2, destX);
				//
				
				moveBlocksAbove(tmpX1, tmpY1, destX);			
			}
		}
	}
}

void moveBlock(int A, int x, int y) {
	BW[ getX(A) ][ getY(A) ]= -1;
	BW[x][y]= A;
	
	BL[A][X]= x;
	BL[A][Y]= y;
}

bool anyBlocksAbove(int A) {
	if (getY(A) != WS-1) {
		if (BW[ getX(A) ][ getY(A)+1 ] != -1) {
			return true;
		}
	}
	
	return false;
}

void moveBlocksAbove(int x, int y, int destX) {
	int srcY= findFreeY(x)-1;	
	int destY= findFreeY(destX);
	
	for (srcY; srcY>y; srcY--) {
		moveBlock(BW[x][srcY], destX, destY);
		destY++;
	}
}

int findFreeX(int avoidX[], int Elements) {
	int out= 0;
	bool Okay= true;
	
	for (out; out<WS; out++) {
		for (int j= 0; j<Elements; j++) {
			if (out == avoidX[j]) {
				Okay= false;
				break;
			}
		}
		
		if (Okay == true) { break; }
		
		Okay= true;
	}
	
	return out;
}

int findFreeY(int x) {
	int y= 0;
	
	for (y; y<WS; y++) {
		if (BW[x][y] == -1) { break; }
	}
	
	return y;
}

void printWorld() {
	for (int x= 0; x<WS; x++) {
		cout << x << ":";
		for (int y= 0; y<WS; y++) {
			if (BW[x][y] != -1) {
				cout << " " << BW[x][y];
			}
		}
		cout << endl;
	}
}

void initializeWorld() {
	for (int x= 0; x<WS; x++) {
		BW[x][0]= x;
		
		for (int y= 1; y<WS; y++) {
			BW[x][y]= -1;
		}
		
		BL[x][X]= x;
		BL[x][Y]= 0;
	}
}

int getX(int A) {
	return BL[A][0];
}
int getY(int A) {
	return BL[A][1];
}

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni »

i seem not to understand this problem correctly.
Hope this helps:
http://online-judge.uva.es/board/viewto ... hlight=101

blank3
New poster
Posts: 3
Joined: Mon Dec 13, 2004 12:05 am

Post by blank3 »

teni_teni wrote:
i seem not to understand this problem correctly.
Hope this helps:
http://online-judge.uva.es/board/viewto ... hlight=101
I got AC! Thank you for your assistance!

Wish you all a lovely day, Blaz.

smart_malk
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:44 am
Location: Canada

SERIOUS problems in java's submition

Post by smart_malk »

I spent the whole day doing P101 and guess what? it seems that it doesnt recognize the java.lang.StringBuffer's delet and indexOf methods!!!

how do I know what's allow and what's not for java??? I dont wanna spend the whole afternoon making my program work but get a compile error because of the poor support for java!!!!!!!!!!!!!!!

SmartMalk

lanlukai
New poster
Posts: 1
Joined: Sun Feb 27, 2005 11:07 am

I am new,please help!

Post by lanlukai »

My c++programme gave this result just as follow.
0: 0
1: 1 2
2:
3:
4:
5: 5 4 6
6:
7: 8 7 9 3
8:
9:
10: 10 11 12
11:
12:
13: 13
14: 14 17
15: 15
16: 16
17:
18: 18
here is my coded:
#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef int elemtype;
struct stacksq{
elemtype *stack;
int top;
int maxsize;
};
stacksq s[30];
int current[30];

void initstack(stacksq &s,int ms)
{ if(ms<=0){cout<<"ms invalid"<<endl;exit(1);}
s.maxsize=ms;
s.stack=new elemtype[ms];
if(!s.stack){
cerr<<"Memory allocation failure!"<<endl;exit(1);
}
s.top=-1;
}
void clearstack(stacksq &s)
{delete []s.stack;
s.stack=0;
s.top=-1;
s.maxsize=0;
}
void allotstack(stacksq &s)
{ stacksq r;
initstack(r,2*s.maxsize);
for(int i=0;i<=s.top;i++)r.stack=s.stack;
r.top=s.top;
clearstack(s);
s=r;
}
void push(stacksq &s,elemtype item)
{ if(s.top==s.maxsize-1)allotstack(s);
s.top++;
s.stack[s.top]=item;
}
elemtype pop(stacksq &s)
{if (s.top==-1){
cerr<<"Stack is empty!"<<endl;
exit(1);
}
s.top--;
return s.stack[s.top+1];
}
elemtype peek(stacksq &s)
{if(s.top==-1){cerr<<"Stack is empty!"<<endl;exit(1);}
return s.stack[s.top];
}
int emptystack(stacksq &s)
{return s.top==-1;}
int fullstack(stacksq &s)
{return s.top==s.maxsize-1;}

void moveonto(int a,int b)
{
int temp;
while(peek(s[current[a]])!=a)
{
temp=pop(s[current[a]]);
push(s[temp],temp);
current[temp]=temp;
}
while(peek(s[current])!=b)
{
temp=pop(s[current]);
push(s[temp],temp);
current[temp]=temp;
}
push(s[current],a);
pop(s[current[a]]);
current[a]=current;
}
void moveover(int a,int b)
{
int temp;
while(peek(s[current[a]])!=a)
{
temp=pop(s[current[a]]);
push(s[temp],temp);
current[temp]=temp;
}
push(s[current],a);pop(s[current[a]]);
current[a]=current;
}
void pileonto(int a,int b)
{
int temp[30];
while(peek(s[current])!=b)
{
temp[0]=pop(s[current]);
push(s[temp[0]],temp[0]);
current[temp[0]]=temp[0];
}
int i=0;
while(peek(s[current[a]])!=a)
{
temp=pop(s[current[a]]);
i++;
}
temp=pop(s[current[a]]);
for(int j=i;j>=0;j--){
push(s[current],temp[j]);
current[temp[j]]=current;
}
}
void pileover(int a,int b)
{
int temp[30],i=0;
while(peek(s[current[a]])!=a)
{
temp=pop(s[current[a]]);
i++;
}
temp=pop(s[current[a]]);
for(int j=i;j>=0;j--){
push(s[current[b]],temp[j]);
current[temp[j]]=current[b];
}
}
void main()
{
int n,onum,a[100],b[100],op[100],temp[30];
int i,k,j=1;char s1[4],s2[4];

cin>>n;
while(j){
cin>>s1;
if (strcmp(s1,"quit")){
cin>>a[j]>>s2>>b[j];
if (!strcmp(s1,"move")&&!strcmp(s2,"onto"))op[j]=0;
if (!strcmp(s1,"move")&&!strcmp(s2,"over"))op[j]=1;
if (!strcmp(s1,"pile")&&!strcmp(s2,"onto"))op[j]=2;
if (!strcmp(s1,"pile")&&!strcmp(s2,"over"))op[j]=3;
j++;
}
else {onum=j-1;j=0;}
}
for(i=0;i<n;i++){
initstack(s,30);
push(s,i);
current=i;
}
for(i=1;i<=onum;i++){
if(current[a]!=current[b[i]]){
if (op[i]==0)moveonto(a[i],b[i]);
if (op[i]==1)moveover(a[i],b[i]);
if (op[i]==2)pileonto(a[i],b[i]);
if (op[i]==3)pileover(a[i],b[i]);
}
}
for(i=0;i<n;i++){
cout<<i<<':';j=0;
while(!emptystack(s[i])){
temp[j]=pop(s[i]);j++;
}
for(k=j-1;k>=0;k--)cout<<' '<<temp[k];
cout<<endl;
}
getchar();
}

Thanks a lot for helping!

Post Reply

Return to “Volume 1 (100-199)”