101 - The Blocks Problem

[Debashis Maitra]

read previous posts


see
http://online-judge.uva.es/board/viewtopic.php?t=10406


i hope this will help you

and i hope you will not open a new thread if there is one already


best of luck

[ckknight]

This keeps giving me a COMPILE ERROR and I have absolutely no idea why, as it compiles and runs perfectly on my machine.

Code: Select all

#include <iostream>

#define loop(var, start, finish) for (int var = (start); var < (finish); ++var)

using namespace std;

main()
{
	int n;
	cin >> n;
	
	int underneath[n]; // what is underneath the block
	int onTop[n]; // what is on top of the block
	loop(i, 0, n)
	{
		underneath[i] = -i - 1;
		onTop[i] = -1;
	}
	
	string command1, command2;
	int a, b;
	while (true)
	{
		cin >> command1;
		if (command1 == "quit")
			break;
		cin >> a >> command2 >> b;
		
		if (command1 == "move")
		{
			int num = onTop[a];
			onTop[a] = -1;
			while (num != -1)
			{
				underneath[num] = -num - 1;
				int tmp = onTop[num];
				onTop[num] = -1;
				num = tmp;
			}
		}
		else
		{
			int num = onTop[a];
			bool good = true;
			while (num != -1)
			{
				if (num == b)
				{
					good = false;
					break;
				}
				num = onTop[num];
			}
			if (!good)
			{
				continue;
			}
			if (underneath[a] >= 0)
			{
				onTop[underneath[a]] = -1;
			}
			underneath[a] = -1;
		}
		if (command2 == "onto")
		{
			int num = onTop[b];
			onTop[b] = -1;
			while (num != -1)
			{
				underneath[num] = -num - 1;
				int tmp = onTop[num];
				onTop[num] = -1;
				num = tmp;
			}
			underneath[a] = b;
			onTop[b] = a;
		}
		else
		{
			int num = b;
			while (true)
			{
				int tmp = onTop[num];
				if (tmp == -1)
				{
					onTop[num] = a;
					underneath[a] = num;
					break;
				}
				num = tmp;
			}
		}
	}
	
	loop(i, 0, n)
	{
		cout << i << ":";
		loop(j, 0, n)
		{
			if (underneath[j] == -i - 1)
			{
				cout << " " << j;
				int num = onTop[j];
				while (num != -1)
				{
					cout << " " << num;
					num = onTop[num];
				}
				break;
			}
		}
		cout << endl;
	}
}

any ideas?

[Vexorian]

I tried in my compiler (GCC) and it doesn't say anything what is odd. The judge will always send you an email with details about your submission, in case of a compile error it will send you an email with info about the line and error.

[helloneo]

try "int main()"
and "#include <string>"

[Carlos]

No files are implicitly included. Please, explicitly include anything you need (string, vector...).

Also, there is an option in your profile where you could get by email your reports, including compile errors.

[ishtiaq ahmed]

can anybody tell me why i faced wrong answer?
please try to help me, Here is my code

Code: Select all

The code is removed after AC

[useasdf_4444]

Hello. I have the following code, checked it bout 10 times, checked every possible test case and it works just fine. Still I get a Wrong Answer! Any ideas?It's driving me crazy!

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void main ()
{
  char command[20];
  char *com,*pos,*stack1,*stack2;
  int boxes,boxtable[25][27],movetable[25],i,j,k,l,st1,st2,spots;
  int check=1;
  #ifndef ONLINE_JUDGE 
  close(0); open("solve.in", O_RDONLY); 
  close(1); open("solve.out", O_WRONLY|O_CREAT|O_TRUNC, 0600); 
  #endif 
  /*initializing table with boxes in default positions and -1 for empty table positions
  table size is set according to maximum possible input values*/
  for(i=0;i<25;i++){
	  for(j=0;j<27;j++){
		  if(j==0||j==1)
			  boxtable[i][j]=i;
		  else
			  boxtable[i][j]=-1;
	  }
  }
  scanf("%d",&boxes);
  getchar();
  gets(command);
  /*processing commands till quit is encountered*/
  while(strcmp(command,"quit")!=0){
	/*spliting command to tokens*/
	com=strtok(command, " ");
	stack1=strtok(NULL, " ");
	pos=strtok(NULL, " ");	
	stack2=strtok(NULL, " ");	
	st1=atoi(stack1);	
	st2=atoi(stack2);
	/*check if box1=box2 or if box1 and box2 are on the same pile*/
	if(st1==st2)
	check=0;
	for(i=0;i<boxes;i++){
		for(j=1;j<=boxes;j++){
			if(boxtable[i][j]==st1||boxtable[i][j]==st2){
				for(k=j+1;k<=boxes;k++){
					if(boxtable[i][k]==st1||boxtable[i][k]==st2)
						check=0;
				}
			}
		}
	}
	/*processing commands*/
	if(check==1){
		if(strcmp(com,"move")==0){
			if(strcmp(pos,"onto")==0){
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st1){
							for(k=j;k<=boxes;k++)
								boxtable[i][k]=boxtable[i][k+1];
						}
					}
				}
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st2){
							for(k=boxes;k>j+1;k--){
								if(boxtable[i][k-1]!=-1)
									boxtable[i][k]=boxtable[i][k-1];
							}
							boxtable[i][j+1]=st1;
						}
					}
				}
			}
			else{
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st1){
							for(k=j;k<=boxes;k++)
								boxtable[i][k]=boxtable[i][k+1];
						}
					}
				}
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st2){
							for(k=j+1;k<=boxes;k++){
								if(boxtable[i][k]==-1){
									boxtable[i][k]=st1;	
									break;
								}
							}
						}
					}
				}
			}
		}
		if(strcmp(com,"pile")==0){
			if(strcmp(pos,"onto")==0){
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st1){
							spots=0;
							for(k=j;k<=boxes;k++){
								if(boxtable[i][k]!=-1){
									movetable[spots]=boxtable[i][k];
									boxtable[i][k]=-1;
									spots++;
								}
							}
						}
					}
				}
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st2){
							for(k=j+1,l=0;l<spots;k++,l++){
								if(boxtable[i][k+spots]==-1){
									boxtable[i][k+spots]=boxtable[i][k];
									boxtable[i][k]=movetable[l];
								}
							}
						}
					}
				}
			}
			else{
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st1){
							spots=0;
							for(k=j;k<=boxes;k++){
								if(boxtable[i][k]!=-1){
									movetable[spots]=boxtable[i][k];
									boxtable[i][k]=-1;
									spots++;
								}
							}
						}
					}
				}
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st2){
							for(k=j+1;k<=boxes;k++){
								if(boxtable[i][k]==-1){
									for(l=0;l<spots;l++)
										boxtable[i][k+l]=movetable[l];
									break;
								}
							}
						}
					}
				}
			}
		}
	}
	/*reset check variable and get next command*/
	check=1;
	gets(command);
  }
  /*print the table with the boxes using specified format (not showing empty table positions)*/
  for(i=0;i<boxes;i++){
	  for(j=0;j<boxes;j++){
		  if(boxtable[i][j]!=-1)
			printf("%d",boxtable[i][j]);
		  if(j==0)
			  printf(":");
		  if(boxtable[i][j+1]!=-1)
		  printf(" ");
	  }
	  printf("\n");
  }
}

[balazs_nyiro]

Hello, I don't understand the
move 7 over 9
command. In the output of Debashis Maitra,
7: 7
but I don't understand why?

Debashis Maitra sample input:
=============================
15
move 10 onto 1
move 8 over 1
move 7 over 9
move 6 over 10
pile 14 over 6
pile 8 onto 5
pile 1 onto 6
move 12 over 1
move 14 onto 9
quit

My output:
===============
0: 0
1:
2: 2
3: 3
4: 4
5: 5 8 6 1 10 12
6:
7:
8:
9: 9 14 7
10:
11: 11
12:
13: 13
14:

[helloneo]

Problem statement says..

move a over b
where a and b are block numbers, 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.

"move 14 onto 9" made that move..

[useasdf_4444]

Clear mind workd always better...found a mistake at pile...onto command and cleared it but still no luck...here goes the change:

Code: Select all

if(strcmp(pos,"onto")==0){
				for(i=0;i<boxes;i++){
					for(j=1;j<=boxes;j++){
						if(boxtable[i][j]==st1){
							spots=0;
							for(k=j;k<=boxes;k++){
								if(boxtable[i][k]!=-1){
									movetable[spots]=boxtable[i][k];
									boxtable[i][k]=-1;
									spots++;
								}
							}
						}
					}
				}

[balazs_nyiro]

Hello, I think the "move 14 onto 9" is good in my program - my output is same as the sample, good output in this case.
my problem the "move 7 over 9"

I don't understand after this command the 7 why stay in the stack 7? (7: 7 the good output, but I think I have to move 7 over 9 - so the stack 7 has to be empty, not?

Thank you, Balazs

[helloneo]

Hmm.. you may not understand the problem correctly..
Because of the command "move 14 onto 9", 7 should go back to its original position..

[balazs_nyiro]

Yes, you are right - I didn't understand the problem - thank you your help!

Balazs

[zxzxas]

Hello, I have the following code. Compile in my PC is OK ,and almost can print the right answer. But upload have many errors. I don't know why. Please.

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define knext *n[k].next

struct head
{
       int a,last,*next;
};

struct num
{
       int a,*next,line;
};


void upout(head h[],num n[],int k)
{
     int *pot;
     if(n[knext].next!=NULL) upout(h,n,knext);
     if(h[knext].last==-1) h[knext].next=&n[knext].a;
     else n[h[knext].last].next=&n[knext].a;
     h[n[k].line].last=k;
     h[knext].last=knext;
     n[knext].line=knext;
     n[k].next=NULL;

}


void move(head h[],num n[],int a,int b)
{
     int *pot;
     pot=h[n[a].line].next;
     if(*pot==a)
     {
                  h[n[a].line].last=-1;
                  h[n[a].line].next=NULL;
     }
     else
     {
         while(*pot!=a)
         {
                       h[n[a].line].last=*pot;
                       pot=n[*pot].next;
         }
         n[h[n[a].line].last].next=NULL;
     }
     n[h[n[b].line].last].next=&n[a].a;
     pot=n[h[n[b].line].last].next;
     while(pot!=NULL)
     {
         n[*pot].line=n[b].line;
         h[n[b].line].last=*pot;
         pot=n[*pot].next;
     }
}


void prt(head h[],num n[],int number)
{
     int*pot;
     for(int i=0;i<number;i++)
     {
             printf("%d(%d):",h[i].a,h[i].last);
             pot=h[i].next;
             while(pot!=NULL)
             {
                             printf(" %d(%d)",*pot,n[*pot].line);
                             pot=n[*pot].next;
             }
             printf("\n");      
     }
}
     


int main()
{
    int number,i,a,b;
    char input[20],fi[10],se[10];
    scanf("%d\n",&number);
    struct head *h=(head*)malloc(number*sizeof(head));
    struct num *n=(num*)malloc(number*sizeof(num));
    for(i=0;i<number;i++)
    {
        h[i].a=i;
        h[i].last=i;
        h[i].next=&(n[i].a);
    }
    for(i=0;i<number;i++)
    {
        n[i].a=i;
        n[i].next=NULL;
        n[i].line=i;
    }
    while(true)
    {
               gets(input);
               if(!strcmp(input,"quit")) break;
               if(!strcmp(input,"print")) prt(h,n,number);
               sscanf(input,"%s %d %s %d",fi,&a,se,&b);
               if(n[a].line==n[b].line) continue;
               if(!strcmp(fi,"move"))
               {
                                     if(n[a].next!=NULL) upout(h,n,a);
                                     if(!strcmp(se,"onto"))
                                     if(n[b].next!=NULL) upout(h,n,b);
                                     move(h,n,a,b);
               }
               else if(!strcmp(fi,"pile"))
               {
                                     if(!strcmp(se,"onto"))
                                     if(n[b].next!=NULL) upout(h,n,b);
                                     move(h,n,a,b);
               }                         
    }                     
    prt(h,n,number);
    return 0;
}

error messages
05336590_24.c:17: parse error before `h'
05336590_24.c: In function `upout':
05336590_24.c:20: `n' undeclared (first use in this function)
05336590_24.c:20: (Each undeclared identifier is reported only once
05336590_24.c:20: for each function it appears in.)
05336590_24.c:20: `k' undeclared (first use in this function)
05336590_24.c:20: `h' undeclared (first use in this function)
05336590_24.c: At top level:
05336590_24.c:31: parse error before `h'
05336590_24.c: In function `move':
05336590_24.c:34: `h' undeclared (first use in this function)
05336590_24.c:34: `n' undeclared (first use in this function)
05336590_24.c:34: `a' undeclared (first use in this function)
05336590_24.c:49: `b' undeclared (first use in this function)
05336590_24.c: At top level:
05336590_24.c:60: parse error before `h'
05336590_24.c: In function `prt':
05336590_24.c:63: parse error before `int'
05336590_24.c:63: `i' undeclared (first use in this function)
05336590_24.c:63: `number' undeclared (first use in this function)
05336590_24.c:63: parse error before `)'
05336590_24.c:66: `h' undeclared (first use in this function)
05336590_24.c:69: `n' undeclared (first use in this function)
05336590_24.c: At top level:
05336590_24.c:74: parse error before `}'
05336590_24.c: In function `main':
05336590_24.c:83: parse error before `struct'
05336590_24.c:87: `h' undeclared (first use in this function)
05336590_24.c:89: `n' undeclared (first use in this function)
05336590_24.c:97: `true' undeclared (first use in this function)

[Debashis Maitra]

Try to compile in GCC or G++ compiler