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

quanghm
New poster
Posts: 5
Joined: Sat Apr 25, 2015 4:00 pm

Re: 101 - The Blocks Problem

Post by quanghm » Sat Apr 25, 2015 5:06 pm

never mind, I realized that it was due to the condition "if a and b are on the same stack then do nothing".

IhateWA
New poster
Posts: 2
Joined: Thu Apr 23, 2015 8:08 am

Re: 101 - The Blocks Problem

Post by IhateWA » Mon Apr 27, 2015 8:58 am

Hello

I have read others' AC code on the Internet.
And,I think my code is act like that.

But,I always get TLE.
Please help me....QQ

thansk

this is my code

Code: Select all

#include<iostream>
#include<string.h>
#include <algorithm>
#include<cstdio>
#define D(x) cout<<#x<<" is "<<x<<endl;
using namespace std;
int Location[30][30];
int Lego_location[30],Location_Lego_num[30];
int Legonum;

void clear_onto(int n)
{
    int n_now_location = Lego_location[n];

    while(Location[n_now_location][Location_Lego_num[n_now_location]-1]!=n)
    {
        int tmp_lego = Location[n_now_location][Location_Lego_num[n_now_location]-1];
        Location_Lego_num[tmp_lego]++;
        Location[tmp_lego][Location_Lego_num[tmp_lego]-1]=tmp_lego;
        Lego_location[tmp_lego]=tmp_lego;
        Location[n_now_location][Location_Lego_num[n_now_location]-1]=-1;
        Location_Lego_num[n_now_location]--;
    }
    return;
}

void move_a_to_b(int a,int b)
{
    int a_now_location = Lego_location[a] , b_now_location = Lego_location[b];
    int c=0;
    for(int i=0;i<Location_Lego_num[a_now_location];i++)
    {
        if(Location[a_now_location][i]==a) c=1;
        if(c!=0)
        {
            Location_Lego_num[b_now_location]++;
            Location[b_now_location][Location_Lego_num[b_now_location]-1] = Location[a_now_location][i];
            Lego_location[Location[a_now_location][i]]=b_now_location;

            Location[a_now_location][i]=-1;
            if(c!=1) c++;
        }
    }
    Location_Lego_num[a_now_location] -= c;
    return;
}


int main()
{
    int a,b;
    string act,act2;
    while(cin>>Legonum && Legonum!=EOF)
    {
        memset(Location,-1,sizeof(Location));

        for(int i=0;i<Legonum;i++)
        {
            Lego_location[i]=i;
            Location[i][0]=i;
            Location_Lego_num[i]=1;
        }
        while(cin>>act && act[0]!='q')
        {
                cin>>a>>act2>>b;
                if(a==b || Lego_location[a]== Lego_location[b]) continue;
                if(act[0]=='m') clear_onto(a);
                if(act2[1]=='n') clear_onto(b);
                move_a_to_b(a,b);
        }
        for(int i=0;i<Legonum;i++)
        {
            cout<<i<<":";
            for(int j=0;j<Location_Lego_num[i];j++)
              if(Location[i][j]!=-1)  cout<<" "<<Location[i][j];
            cout<<endl;
        }
    }
    return 0;
}
this is someone's AC code

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
  int position[30][2];
  int block[30][30];
  int top[30];
  int n;
  char action1[10], action2[10];
  int a, b, ax, ay, bx, by;

  while( scanf( "%d", &n ) != EOF ){
    for( int i = 0 ; i < n ; i++ ){
      position[i][0] = i;
      position[i][1] = 0;
      block[i][0] = i;
      top[i] = 1;
    }
    while( scanf( "%s", action1 ) != EOF && strcmp( action1, "quit" ) ){
      scanf( "%d%s%d", &a, action2, &b );

      ax = position[a][0];
      ay = position[a][1];
      bx = position[b][0];
      by = position[b][1];

      if( ax == bx ) continue;

      if( !strcmp(action1, "move") ){
        for( int i = ay+1 ; i < top[ax] ; i++ ){
          position[block[ax][i]][0] = block[ax][i];
          position[block[ax][i]][1] = top[block[ax][i]];
          block[block[ax][i]][top[block[ax][i]]++] = block[ax][i];
        }
        top[ax] = ay+1;
      }
      if( !strcmp(action2, "onto") ){
        for( int i = by+1 ; i < top[bx] ; i++ ){
          position[block[bx][i]][0] = block[bx][i];
          position[block[bx][i]][1] = top[block[bx][i]];
          block[block[bx][i]][top[block[bx][i]]++] = block[bx][i];
        }
        top[bx] = by+1;
      }

      for( int i = ay ; i < top[ax] ; i++ ){
        position[block[ax][i]][0] = bx;
        position[block[ax][i]][1] = top[bx];
        block[bx][top[bx]++] = block[ax][i];
      }
      top[ax] = ay;
    }

    for( int i = 0 ; i < n ; i++ ){
      printf( "%d:", i );
      for( int j = 0 ; j < top[i] ; j++ )
        printf( " %d", block[i][j] );
      printf( "\n" );
    }
  }

  return 0;
}

bupean
New poster
Posts: 1
Joined: Sat Aug 15, 2015 3:22 pm

Re: 101 - The Blocks Problem

Post by bupean » Sat Aug 15, 2015 3:31 pm

Here's my code for the Blocks Problem.
I have tried multiple test cases which the code satisfied.
But after submission, I am still getting "Wrong answer" as the verdict.
Can anyone please point out the mistake?

Code: Select all

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

int main()
{
	/*Variable declarations*/
	int n, i, j;
	char command[4];
	int moveFlag, pileFlag, ontoFlag, overFlag, failFlag;
	int a, b, aXPos, aYPos, bXPos, bYPos, returnPos;
	int blockPos[25][25];	
	
	scanf("%d",&n);

	/*First input is number of blocks*/
	/*Initially the positions of the blocks
	are corresponding to the array positions*/
	for(i=0;i<n;i++)
	{
		blockPos[i][0]=i; 	
		blockPos[i][1]=-1;
	}
	/*Keep on fetching commands till quit is encountered*/	
	while(1)
	{
		aXPos=-1;
		aYPos=-1;
		bXPos=-1;
		bYPos=-1;
		failFlag=0;
		overFlag=0;
		ontoFlag=0;
		moveFlag=0;
		pileFlag=0;
		/*Take in the first command*/
		scanf("%s",command);
		/*Set flag as per command selected*/
		if(command[0]=='m')
			moveFlag=1;
		else if(command[0]=='p')
			pileFlag=1;
		else if(command[0]=='q')
			break;
		else 
		{
			failFlag=1;
			break;
		}
		/*Accept the value of a*/
		scanf("%d",&a);
		/*Accept the second command*/
		scanf("%s",command);
		/*Set flag as per command selected*/
		if(command[1]=='v')
			overFlag=1;
		else if(command[1]=='n')
			ontoFlag=1;
		else
		{
			failFlag=1;
			break;
		}
		/*Accept value of b*/
		scanf("%d",&b);
		if(a>=n||b>=n||a<0||b<0) continue;
		if(a==b) continue;
		/*Find out position of a and b*/
		for(i=0;i<n;i++)
			for(j=0;blockPos[i][j]!=-1;j++)
			{
				if(blockPos[i][j]==a)
				{
					aXPos=i;
					aYPos=j;
				}
				else if(blockPos[i][j]==b)
				{
					bXPos=i;
					bYPos=j;
				}
			}
		/*printf("%d %d %d %d\n",aXPos,aYPos, bXPos, bYPos);*/
		if(aXPos==bXPos) 
			continue;
		/*There are three operations performed by the arm:
		1. empty post a (move onto, move over) 
		2. empty post b (move onto, pile onto)
		3. move a after b*/
		/*Empty post a if operation is not pile*/
		if(!pileFlag){
			for(i=aYPos+1;blockPos[aXPos][i]!=-1;i++)
			{
				returnPos = blockPos[aXPos][i];
				blockPos[aXPos][i]=-1;
				blockPos[returnPos][0] = returnPos;
				blockPos[returnPos][1] = -1;
			}
			/*blockPos[aXPos][aYPos+1]=-1;	*/
		}
		/*Empty post b if operation is not over*/
		if(!overFlag){
                               for(i=bYPos+1;blockPos[bXPos][i]!=-1;i++)
                               {
                                       returnPos = blockPos[bXPos][i];
				blockPos[bXPos][i]=-1;
                                       blockPos[returnPos][0] = returnPos;
				blockPos[returnPos][1] = -1;
                               }      
                               /*blockPos[bXPos][bYPos+1]=-1;*/
		}
		/*Move a after b*/
		/*move to end of b*/
		for(i=bYPos;blockPos[bXPos][i]!=-1;i++);
		bYPos=i-1;
		for(i=aYPos;blockPos[aXPos][i]!=-1;i++)
		{
			blockPos[bXPos][++bYPos]=blockPos[aXPos][i];
			blockPos[aXPos][i] = -1;
			/*printf("%d\n",blockPos[bXPos][bYPos]);*/
		}
		blockPos[bXPos][bYPos+1]=-1;
						
	};
	if(failFlag==1)
	{
		/*do nothing*/
	}
	else
	{
		/*display*/
		for(i=0;i<n;i++)
		{
			printf("%d:",i);
			for(j=0;blockPos[i][j]!=-1;j++)
				printf(" %d",blockPos[i][j]);
			printf("\n");
		}
	}
	return 0;
}

Taviiir
New poster
Posts: 1
Joined: Sat Aug 22, 2015 5:53 pm

101-The block problem

Post by Taviiir » Sat Aug 22, 2015 6:05 pm

Can anyone help me?
I got runtime error in C and WA in C++.My input and output seems to be okey. Where is the bug?
The code is:

Code: Select all

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

void move_onto(int,int,int);
void move_over(int,int,int);
void pile_onto(int,int,int);
void pile_over(int,int,int);
void display(int);


 int ar[25][25];


int main()
{

    int n,a,b,i,j;
     scanf("%d",&n);


    char s1[5],s2[5];
     for(i=0;i<n;i++)
     for(j=0;j<n;j++)
     ar[i][j]=-1;

    for(i=0;i<n;i++)
        ar[i][0]=i;


    while(scanf("%s",s1)==1) {
     if(strcmp(s1,"quit")==0 )
        display(n);
     else
    scanf("%d%s%d",&a,s2,&b);

       if(a==b || a>=n || b>=n) continue;


       else if(strcmp(s1,"move")==0 && strcmp(s2,"onto")==0)
        move_onto(n,a,b);

       else if(strcmp(s1,"move")==0 && strcmp(s2,"over")==0)
        move_over(n,a,b);

        else if(strcmp(s1,"pile")==0 && strcmp(s2,"onto")==0)
        pile_onto(n,a,b);

        else if(strcmp(s1,"pile")==0 && strcmp(s2,"over")==0)
        pile_over(n,a,b);

        else
            continue;

    }




}

void move_onto(int n,int a,int b)
{
    int i,j,p,q,x,y,h,a1,a2,x1;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==a)
        {
            x=i;
            y=j;
            break;
        }
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==b)
        {
            p=i;
            q=j;
            break;
        }
    }

    if(x==p) return ;

     for(i=y+1;i<n;i++)
     {
         j=ar[x][i];
         if(j>=0)
         {
             ar[j][0]=j;
             ar[x][i]=-1;
         }
         else if(j==-1) break;
     }

     for(i=q+1;i<n;i++)
     {
         j=ar[p][i];
         if(j>=0)
         {
             ar[j][0]=j;
             ar[p][i]=-1;
         }
         else if(j=-1) break;
     }

             ar[p][q+1]=ar[x][y];
             ar[x][y]=-1;

             }




void move_over(int n,int a,int b)
{
    int i,j,p,q,x,y,h,a1,a2,y1;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==a)
        {
            x=i;
            y=j;
            break;
        }
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==b)
        {
            p=i;
            q=j;
            break;
        }
    }

    if(x==p) return ;

     for(i=y+1;i<n;i++)
     {
         j=ar[x][i];
         if(j>=0)
         {
             ar[j][0]=j;
             ar[x][i]=-1;
         }
         else if(j==-1) break;
     }

             for(i=q+1;i<n;i++)

             {
                 if(ar[p][i]==-1)
                 {
                     ar[p][i]=ar[x][y];
                     ar[x][y]=-1;
                        break;
                 }
             }

}

void pile_onto(int n,int a,int b)
{
    int i,j,p,q,x,y,h,a1,a2,y1,x1;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==a)
        {
            x=i;
            y=j;
            break;
        }
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==b)
        {
            p=i;
            q=j;
            break;
        }
    }

    if(x==p) return ;

     for(i=q+1;i<n;i++)
     {
         j=ar[p][i];
          if(j>=0)
         {
             ar[j][0]=j;
             ar[p][i]=-1;
         }
         else if(j==-1) break;
     }


                j=q+1;
             for(i=y;i<n;i++)

             {
                 if((ar[x][i]>=0) && (ar[p][j]==-1))
                 {
                     ar[p][j]=ar[x][i];
                     ar[x][i]=-1;
                     j++;
                     }
                    else break;

             }
}



void pile_over(int n,int a,int b)
{
    int i,j,p,q,x,y,h,a1,a2,y1;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==a)
        {
            x=i;
            y=j;
            break;
        }
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
    {
        if(ar[i][j]==b)
        {
            p=i;
            q=j;
            break;
        }
    }

    if(x==p) return ;

    for(i=y;i<n;i++)
        for(j=q+1;j<n;j++)
        {
            if(ar[x][i]!=-1)
            {
                if(ar[p][j]==-1) {
                ar[p][j]=ar[x][i];
                ar[x][i]=-1;
                }
            }
            else if(ar[x][i]==-1) break;
        }


}

void display(int n)
{
    int i,j;
    for(j=0;j<n;j++)
        {
            printf("\n%d: ",j);
            for(i=0;i<n;i++)
            {
                if(ar[j][i]!=-1)
                    printf("%d ",ar[j][i]);
            }
        }
        printf("\n");
        main();
}

Frivolian
New poster
Posts: 1
Joined: Tue Sep 22, 2015 1:52 pm

Re: 101 - The Blocks Problem

Post by Frivolian » Tue Sep 22, 2015 1:57 pm

Could anyone please tell me what is the problem with this code against ANSI C?

It gets accepted in C++, but Runtime Error in ANSI C.

Many thanks!

Code: Select all

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

int world[25][25];
int size = 0;

void quit();
void moveOnto(int a, int b);
void moveOver(int a, int b);
void pileOnto(int a, int b);
void pileOver(int a, int b);
void clearAbove(int i, int j);
void initWorld();

int checkSameStacks(int a, int b);

int main()
{
	char cmd1[10], cmd2[10];
	int p1, p2;

	scanf("%d", &size);
	initWorld();

	while (scanf("%s", cmd1)){
		if(strcmp(cmd1, "quit") == 0){ /*quit*/
			quit();
			break;
		}
		else{ 
			scanf("%d", &p1);
			scanf("%s", cmd2);
			scanf("%d", &p2);
			if (p1 == p2) continue;
			if (p1 >= size || p2 >= size || p1<0 || p2<0) continue;
			if (checkSameStacks(p1, p2)==0) continue;
			
			
			/*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.*/
			
			if (strcmp(cmd1,"move") == 0){ /*move*/
				if (strcmp(cmd2,"onto") == 0){ /*onto*/
					moveOnto(p1, p2);
				}
				else{ /*over*/
					moveOver(p1, p2);
				}
			}
			else{ /*pile*/
				if (strcmp(cmd2,"onto") == 0){ /*onto*/
					pileOnto(p1, p2);
				}
				else{ /*over*/
					pileOver(p1, p2);
				}
			}
		}
	}

	return 0;
}


void quit(){
	/*If there is at least a block on it, the colon must be followed by one space, 
	followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. 
	Don't put any trailing spaces on a line.*/
	int i, j;

	for (i = 0; i < size; i++){
		printf("%d:", i);
		for (j = 0; j < size; j++){
			if (world[i][j] == -1) break;
			printf(" %d", world[i][j]);
		}
		printf("\n");
	}
	return;
}

void moveOnto(int a, int b){
	/*puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.*/
	int i=-1, j=-1, i_a=-1, j_a=-1, i_b=-1, j_b=-1;
	for (i = 0; i < size; i++){
		for (j = 0; j < size; j++){/*search for the two blocks*/
			if (world[i][j] == a){
				i_a = i;
				j_a = j;
			}
			if (world[i][j] == b){
				i_b = i;
				j_b = j;
			}
		}
		if ((i_a != -1) && (i_b != -1)){
			if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
			else{/*otherwise clear it*/
				clearAbove(i_a, j_a);
				clearAbove(i_b, j_b);
			}
			break;
		}
	}
	/*The program should only arrive here if the command is valid
	Put block a onto block b, clear block a from its previous place and finish the command*/
	world[i_b][j_b + 1] = world[i_a][j_a];
	world[i_a][j_a] = -1;

	return;
}

void moveOver(int a, int b){
	/* puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.*/
	
	int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
	for (i = 0; i < size; i++){
		for (j = 0; j < size; j++){/*search for the two blocks*/
			if (world[i][j] == a){
				i_a = i;
				j_a = j;
			}
			if (world[i][j] == b){
				i_b = i;
				j_b = j;
			}
		}
		if ((i_a != -1) && (i_b != -1)){
			if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
			else{/*otherwise clear it*/
				clearAbove(i_a, j_a);
			}
			break;
		}
	}
	/*The program should only arrive here if the command is valid
	Put block a over block b, clear block a from its previous place and finish the command*/
	
	while (j_b < size){
		if (world[i_b][j_b] == -1){
			world[i_b][j_b] = world[i_a][j_a];
			world[i_a][j_a] = -1;
			return;
		}
		j_b++;
	}

	/*If it arrives here, something is messed up :)*/
	printf("Kaki van :)");
	return;
}

void pileOnto(int a, int b){
	/*moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. 
	All blocks on top of block b are moved to their initial positions prior to the pile taking place. 
	The blocks stacked above block a retain their order when moved.*/
	
	int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
	for (i = 0; i < size; i++){
		for (j = 0; j < size; j++){/*search for the two blocks*/
			if (world[i][j] == a){
				i_a = i;
				j_a = j;
			}
			if (world[i][j] == b){
				i_b = i;
				j_b = j;
			}
		}
		if ((i_a != -1) && (i_b != -1)){
			if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
			else{/*otherwise clear it*/
				clearAbove(i_b, j_b);
			}
			break;
		}
	}
	/*The program should only arrive here if the command is valid
	Pile the stack of block a onto block b, clear the stack of block a from its previous place and finish the command*/
	j_b++;
	while (j_a < size && j_b < size){
		world[i_b][j_b] = world[i_a][j_a];
		world[i_a][j_a] = -1;
		j_a++;
		j_b++;/*possible out of bounds?*/
	}

	return;
}

void pileOver(int a, int b){
	/*puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. 
	The blocks stacked above block a retain their original order when moved.*/
	
	int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
	for (i = 0; i < size; i++){
		for (j = 0; j < size; j++){/*search for the two blocks*/
			if (world[i][j] == a){
				i_a = i;
				j_a = j;
			}
			if (world[i][j] == b){
				i_b = i;
				j_b = j;
			}
		}
		if ((i_a != -1) && (i_b != -1)){
			if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
			break;
		}
	}
	/*The program should only arrive here if the command is valid
	Pile the stack of block a over the stack of block b, clear the stack of block a from its previous place and finish the command*/
	
	while (j_b < size && world[i_b][j_b] != -1){/*search for the first available place in the stack of block b*/
		j_b++;
	}

	while (j_a < size && j_b < size){
		world[i_b][j_b] = world[i_a][j_a];
		world[i_a][j_a] = -1;
		j_a++;
		j_b++;
	}

	return;
}

int checkSameStacks(int a, int b){

	int i, j, stackA = -1, stackB = -1;

	for (i = 0; i < size; i++){
		for (j = 0; j < size; j++){
			if (world[i][j] == a) stackA = i;
			if (world[i][j] == b) stackB = i;
			if (stackA != -1 && stackB != -1){
				if (stackA == stackB) return 0;
				else return 1;
			}
		};
	}
	return 0;
}

void clearAbove(int i, int j){
	int value;

	if (j < size){
		for (++j; j < size; j++){
			value = world[i][j];
			world[value][0] = value;
			world[i][j] = -1;
		}
	}
}

void initWorld(){
	
	int i, j;
	
	for (i = 0; i < size; i++){
		world[i][0] = i;
		for (j = 1; j < size; j++){
			world[i][j] = -1;
		}
	}
	return;
}

pavan.tc
New poster
Posts: 1
Joined: Wed Nov 25, 2015 4:57 pm

Re: 101 - The Blocks Problem

Post by pavan.tc » Wed Nov 25, 2015 5:03 pm

My program hit a "runtime error". That is all the information I have in my mail. Couple of questions:
1. The input, as mentioned in the problem, can be assumed to be limited to 25 blocks. Do any of the test cases enter a number larger than this limit?
2. Can I get the test case that generated this error?
3. Can the program output be passed on after a test failure?

Thanks,
Pavan

Post Reply

Return to “Volume 1 (100-199)”