101 - The Blocks Problem

[HKcow]

Thank you very much. I am going to fix it now

[HKcow]

I have fixed it, however,
it god WA now, no run time error, can you find another wrong case for my programme..
[cpp]#include <stdio.h>

int table[30][30];

bool findpos(int t1, int t2, int &s1, int &p1, int &s2, int &p2) {
if (t1==t2)
return false;
int i, j, k=0;
for (i=0; k!=2; i++)
for (j=0; (k!=2) && (table[j]!=-1); j++) {
if (table[j]==t1) {
s1=i;
p1=j;
k++;
}
if (table[j]==t2) {
s2=i;
p2=j;
k++;
}
}
if (s1==s2)
return false;
else
return true;
}

void move(int s1, int p1, bool whole, int s2, int p2, bool top) {
int i, k, a;
a=1;
if (whole)
for (; table[s1][p1+a]!=-1; a++);

for (k=p2+1; table[s2][k]!=-1; k++);
if (top)
table[s2][k+a]=-1;
else {
for (i=k; i>p2; i--)
table[s2][i+a]=table[s2];
k=p2+1;
}
for (i=0; i<a; i++)
table[s2][k+i]=table[s1][p1+i];
if (whole)
table[s1][p1]=-1;
else
for (i=p1; table[s1]!=-1; i++)
table[s1]=table[s1][i+1];
}

void main() {
int i, j, n, s, d, s1, s2, p1, p2;
bool tp;
char c1[5], c2[5];
scanf("%d", &n);
for (i=0; i<n; i++) {
table[0]=i;
table[1]=-1;
}
scanf("%s", c1);
while (c1[0]!='q') {
scanf("%d %s %d", &s, c2, &d);
if ((s<n) && (s>=0) && (d<n) && (d>=0) && (findpos(s, d, s1, p1, s2, p2))) {
if (c1[0]=='m')
tp=false;
else
tp=true;
if (c2[1]=='n')
move(s1, p1, tp, s2, p2, false);
else
move(s1, p1, tp, s2, p2, true);
}
scanf("%s", c1);
}
for (i=0; i<n; i++) {
printf("%d:", i);
for (j=0; table[j]!=-1; j++)
printf(" %d", table[j]);
printf("\n");
}
}[/cpp]

[Moni]

Hi there!

I used two methods to solve this. At first it gave me run-time error and when I made the table size more than about 75 it gave me not run-time error but time limit exit. So my suggestion is to increase your table size.

Good Luck!

[cyfra]

Hi!

Sorry for not answering for such a long time but I was too usy to do so.
So here is your explanation:

1:1 2 6
2:3
3:4 5 7
4:
5:
6:
7:
After execute command "move 4 onto 1"
1:1 4
2:3 2
3:
4:
5:5
6:6
7:7

There is written after returning any blocks that are stacked on top. That means every block that is above a and b.


If there is move a OVER b there is:
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.

Here you are returnig all blocks that are above block a. you move the block a on the TOP of the stack with block b.

pile a onto b

Here you remove all the block that were above block b. and move blocks that are above the block a (with block a) on the block b.

I hope you understand this.

If not just write me e-mail and I will try to explain it to you.

Good Luck

[shuhag_123]

can any body explain me about prob 110

[Moni]

Hello! Everybody!

I am in great trouble with this code. It is giving "Run-Time Error" in the judge's machine. I have compiled it in VC++, TC++ and also in BC++, but there was neither error nor warning. I think not only the sample input output was correct but also this is the correct solution for the problem 101.
Can any C++ expert help me???

[cpp]
#include<stdio.h>
#include<iostream.h>
#include<string.h>

#define ROW 100
#define COL 100

int i=0,j=0,t=0,f=0;

int grid[ROW][COL];
int num=0;

inline void init(void)
{
memset(grid,-1,sizeof(grid)); // Initialize all array to -1 as it can differ from data;
}


void setgrid(int &data);
void print(void);
void locate(int &data,int &x,int &y);
inline int check(int &ar,int &ac,int &br,int &bc);
void back(int &row,int &col);
void move_onto(int Chk,int &a,int &b,int &ar,int &ac,int &br,int &bc);
void move_over(int Chk,int &a,int &b,int &br,int &bc);
void pile_onto(int Chk,int &a,int &b,int &ar,int &ac,int &br,int &bc);
void pile_over(int Chk,int &a,int &b,int &br,int &bc);


void back(int &row,int &col)
{
for(i=(ROW-1);i!=row;i--)
{
if(grid[col]!=-1)
{
grid[0][grid[col]]=grid[col];
grid[col]=-1;
}
}
}

void setgrid(int &data)
{
for(i=0;i<data;i++)
grid[0]=i;
}

void print(void)
{
for(j=0,t=0;j<COL;j++)
{
if(t<num)
{
printf("%2d:",t);

for(i=0;i<ROW;i++)
{
if(grid[j]!=-1)
cout << ' ' << grid[j];
}

cout << endl;
t++;
}
}
}

void locate(int &data,int &x,int &y)
{
for(i=0;i<ROW;i++)
{
f=0;
for(j=0;j<COL;j++)
if(grid[j]==data)
{
x=i;
y=j;

f=1; // If you find the data and its location BREAK the loop;
break;
};
if(f==1)
break;
}
}

int check(int &ar,int &ac,int &br,int &bc)
{
if(ac==bc)
return -1; // If in same stack return -1;
if(grid[ar+1][ac]>0 && grid[br+1][bc]>0) // if both have above something return 3
return 3;
if(grid[ar+1][ac]>0) // if somehting above a return 1
return 1;
if(grid[br+1][bc]>0)
return 2; // if something above b return 2

return 0;
}

void move_onto(int Chk,int &a,int &b,int &ar,int &ac,int &br,int &bc)
{
if(Chk==0)
{
grid[ar][ac]=-1;
grid[br+1][bc]=a;
}

else if(Chk==3)
{
back(ar,ac);
back(br,bc);

move_onto(check(ar,ac,br,bc),a,b,ar,ac,br,bc);
}

else if(Chk==1)
{
back(ar,ac);
move_onto(check(ar,ac,br,bc),a,b,ar,ac,br,bc);
}

else if(Chk==2)
{
back(br,bc);
move_onto(check(ar,ac,br,bc),a,b,ar,ac,br,bc);
}
}

void move_over(int Chk,int &a,int &b,int &br,int &bc)
{
int ar,ac;
locate(a,ar,ac);
int row=br,col=bc;

if(Chk==2 || Chk==0)
{
if(grid[row+1][col]==-1)
move_onto(Chk,a,b,ar,ac,row,col);
else
{
for(int t=row;t<ROW;t++)
if(grid[t][col]==-1)
{
row=t-1;
break;
}
move_onto(check(ar,ac,row,col),a,grid[row][col],ar,ac,row,col);
}
}

else if(Chk==3 || Chk==1)
{
back(ar,ac);
move_over(check(ar,ac,br,bc),a,b,br,bc);
}
}

void pile_onto(int Chk,int &a,int &b,int &ar,int &ac,int &br,int &bc)
{
if(Chk==0 || Chk==2)
move_onto(Chk,a,b,ar,ac,br,bc);

else if(grid[br+1][bc]==-1)
{
while(grid[ar][ac]!=-1)
{
grid[++br][bc]=grid[ar][ac];
grid[ar][ac]=-1;
ar++;
}
}

else if(Chk==3 || Chk==1)
{
back(br,bc);
pile_onto(check(ar,ac,br,bc),a,b,ar,ac,br,bc);
}

}

void pile_over(int Chk,int &a,int &b,int &br,int &bc)
{
int row=br;
int col=bc;
int ar,ac;
locate(a,ar,ac);

if(grid[row+1][col]==-1)
pile_onto(Chk,a,b,ar,ac,br,bc);

else
{
for(int t=row;t<ROW;t++)
if(grid[t][col]==-1)
{
row=t-1;
break;
}

pile_onto(check(ar,ac,row,col),a,grid[row][col],ar,ac,row,col);
}
}

int main()
{
char command[5]={0},type[5]={0};
int from=0,to=0;

cin >> num;

init();
setgrid(num);

while(strcmp(command,"quit")!=0)
{
cin >> command;

if(strcmp(command,"move")==0)
{
cin >> from;
cin >> type;
cin >> to;

int fr,fc,tr,tc;
locate(from,fr,fc);
locate(to,tr,tc);

int Chk=check(fr,fc,tr,tc);

if(Chk==-1)
continue;
else if(strcmp(type,"onto")==0)
{
move_onto(Chk,from,to,fr,fc,tr,tc);
}
else if(strcmp(type,"over")==0)
{
move_over(Chk,from,to,tr,tc);
}
}
else if(strcmp(command,"pile")==0)
{
cin >> from;
cin >> type;
cin >> to;

int fr,fc,tr,tc;
locate(from,fr,fc);
locate(to,tr,tc);

int Chk=check(fr,fc,tr,tc);

if(Chk==-1)
continue;
else if(strcmp(type,"onto")==0)
{
pile_onto(Chk,from,to,fr,fc,tr,tc);
}
else if(strcmp(type,"over")==0)
{
pile_over(Chk,from,to,tr,tc);
}
}
}

print();

return 0;
}
[/cpp]

[Moni]

Hai !
What do you mean 101 or 110 ???

[Archer]

Hi,

following problem: what does pile a over b do if b is in the stack above a?

Example: (from the problem example data)
after the move instructions, I have:

0: 0
1: 1 9 8 7 6
2: 2
3: 3
4: 4
5: 5
6: 6
7:
8:
9:

The next command is "pile 8 over 6", but 6 is in the stack containing 8. So how is the program supposed to react in this case?

Thanks for any help
Archer

[yiuyuho]

Read the problem, it says:
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

in the input, so in your case you should not do anything to the blocks

[yiuyuho]

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.

[yiuyuho]

There are several places I don't quite get in your code
for instance, why are you printing from 0 instead of from 1?

[Moni]

The boxes number is N and the boxes start from 0 to (N-1) is that correct?

[yiuyuho]

Then you mught need to change grid[ar+1][ac]>0 and corresponding checkings to >=0 since a 0 is also a block.

[Archer]

Hi,

I don't quite understand why I get a WA error with this code: (works perfectly with the example input)
[c]
/* @JUDGE_ID: 21775WY 101 C */
/* Problem Number 101 */
/* Robert Spielmann (Archer)*/
/* rsp@byteforge.org */

void m_onto(int ii, int jj);
void m_over(int ii, int jj);
void p_onto(int ii, int jj);
void p_over(int ii, int jj);
void clear_top(int ii);
void print_world();

struct box {
int id; /* number of box */
int position; /* position */
int height; /* height in stack */
} boxes[25];

char world[25][26];
char command[2][5], c;
char line[16];
int a, b, i, j, m, n, on, worldsize;

int main(void) {
/* inits */
memset(world, 0x20, 650);
memset(command, 0, 10);

/* read world size */
scanf("%i", &worldsize);
c = getchar();

/* put boxes on initial positions */
for(i=0; i<worldsize; i++) {
boxes.id = boxes.position = i;
boxes.height = 0;
world[0] = i;
}

i=0;

/* parse commands until "quit" is found */
while(1) {
/* read a line up to \n */
while((c=getchar())!='\n')
line[i++] = c;
line='\0'; /* terminate line */
i=0;
/* if only one argument: quit */
if(sscanf(line, "%s %i %s %i", &command[0], &a, &command[1], &b) < 4)
break;
/* set vars for function call decision */
if(strcmp(command[0], "move")==0) m=1; else m=0;
if(strcmp(command[1], "onto")==0) on=1; else on=0;

/* switch to decide which function to call */
switch(m) {
case 1:
if(on==1) m_onto(a, b);
else m_over(a, b);
break;
case 0:
if(on==1) p_onto(a, b);
else p_over(a, b);
break;
}
}
print_world();
}

void m_onto(int ii, int jj) {
if(ii==jj) return;
if(boxes[ii].position==boxes[jj].position) return;
clear_top(ii); clear_top(jj);
world[boxes[jj].position][boxes[jj].height+1] = ii;
world[boxes[ii].position][boxes[ii].height] = 0x20;
boxes[ii].position = boxes[jj].position;
boxes[ii].height = boxes[jj].height+1;
}

void m_over(int ii, int jj) {
int nw = boxes[jj].position;
int nh = boxes[jj].height;

if(ii==jj) return;
if(boxes[ii].position==nw) return;

while(world[nw][nh]!=0x20) nh++;
world[nw][nh] = ii;
world[boxes[ii].position][boxes[ii].height]=0x20;
boxes[ii].position=nw;
boxes[ii].height = nh;
}

void p_onto(int ii, int jj) {
int nh = boxes[jj].height+1;
int nw = boxes[jj].position;
int ow = boxes[ii].position;
int oh = boxes[ii].height;

if(ii==jj) return;
if(nw==ow) return;

clear_top(jj);
for( ; world[ow][oh] != 0x20 ; nh++, oh++) {
world[nw][nh] = world[ow][oh];
world[ow][oh] = 0x20;
boxes[ii].position = nw;
boxes[ii].height = nh;
}
}

void p_over(int ii, int jj) {
int nh = boxes[jj].height+1;
int nw = boxes[jj].position;
int ow = boxes[ii].position;
int oh = boxes[ii].height;

if(ii==jj) return;
if(ow == nw) return;

for( ; world[ow][oh] != 0x20 ; nh++, oh++) {
world[nw][nh] = world[ow][oh];
world[ow][oh] = 0x20;
boxes[ii].position = nw;
boxes[ii].height = nh;
}
}

/* fn to unstack boxes above box ii */
void clear_top(int ii) {
int temp;
int where = boxes[ii].position;
int height = boxes[ii].height+1;
while(1) {
temp = world[where][height];
if(temp==0x20) break;
world[temp][0]=temp;
world[where][height]=0x20;
boxes[temp].position = boxes[temp].id;
boxes[temp].height = 0;
++height;
}
}

void print_world() {
for(i=0; i<worldsize; i++) {
printf("%2i:", i);
j=0;
while(world[j]!=0x20)
printf(" %i", world[j++]);
printf("\n");
}
}
[/c]

[Archer]

Hi,

I'm a little unsure about the output format for problem #101. The example looks like the position numbers consist of 2 digits, like

[c]printf("%2i:", pos);[/c]

is that correct or does it have to be

[c]printf("%i:", pos);[/c] ?