101 - The Blocks Problem

[Jubba]

I have no clue what I am doing wrong here. I have tested everything I can think of and I am convinced my code is correct but continue to get WA sent back to me. I' m wondering now if I am submitting the code incorrectly or if there is simply a test case I cannot seem to think of. This is the exact text I pasted into MS Outlook and sent the judge.

[c]
/*@BEGIN_OF_SOURCE_CODE*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* @JUDGE_ID: 22113ZY 101 C */

#define MAXSIZE 24

void initializeBlocks(int M[MAXSIZE][MAXSIZE], int num)
{
int i,j;

for (i = 0; i < num ; i++)
{
for (j = 0; j < num ; j++)
{
if (j == 0)
M[j] = i;
else
M[j] = -1;
}
}

return;
}

void display(int M[MAXSIZE][MAXSIZE], int num)
{
int i,j;

for (i = 0; i < num ; i++)
{
printf("%d: ", i);

for (j = 0; j < num ; j++)
{
if (M[j] != -1)
printf("%d ", M[j]);
}

printf("\n");
}

return;
}

void clear(int M[MAXSIZE][MAXSIZE], int num, int block)
{
int i,j;

for (i = 0; i < num ; i++)
{
for (j = 0; j < num ; j++)
{
if (M[j] == block)
{
j++;
while(j < num && M[j] != -1)
{
M[(M[j])][0] = M[j];
M[j] = -1;
j++;
}
return;
}
}
}
}

void stack(int M[MAXSIZE][MAXSIZE], int num, int fromBlock, int toBlock)
{
int i,j;
int *fp, *tp;

for (i = 0; i < num ; i++)
{
for (j = 0; j < num ; j++)
{
if (M[j] == fromBlock)
fp = &M[i][j];

if (M[i][j] == toBlock)
tp = &M[i][j];
}
}

while (*tp != -1)
tp++;

while (*fp != -1)
{
*tp = *fp;
*fp = -1;
fp++;
tp++;
}
}

int main(void)
{

/* FILE *inp, *outp; */
int i, j, k;
int quit = 0;
int numBlocks = 0;
int ignore = 0;
int matrix[MAXSIZE][MAXSIZE];
char line[100];
int a,b;
char cmd[5];
char action[6];

/*
if ((inp = fopen("prob101input.txt","r")) == NULL)
{
printf("FILE READ ERROR");
exit(EXIT_FAILURE);
}

if ((outp = fopen("prob101output.txt","w")) == NULL)
{
printf("FILE WRITE ERROR");
exit(EXIT_FAILURE);
}
*/

fgets(line,100,stdin);
sscanf(line,"%d", &numBlocks);
if (numBlocks < 1 || numBlocks > 24)
return 0;
initializeBlocks(matrix, numBlocks);
display(matrix, numBlocks);

while (!feof(stdin))
{
fgets(line,100,stdin);
sscanf(line,"%s%d%s%d", cmd, &a, action, &b);

if (strcmp(cmd,"quit") == 0)
{
display(matrix, numBlocks);
return 0;
}

if (a == b)
continue;

for (i = 0; i < numBlocks ; i++)
{
for (j = 0; j < numBlocks ; j++)
{
if (matrix[i][j] == a)
{
k = 0;
while (k < numBlocks && matrix[i][k] != -1)
{
if (matrix[i][k] == b)
{
ignore = 1;
goto IgnoreThis;
}
k++;
}
}
}
}

IgnoreThis:
if (ignore)
{
ignore = 0;
continue;
}

if (strcmp(cmd,"move") == 0)
{
if (strcmp(action,"onto") == 0)
{
clear(matrix, numBlocks, a);
clear(matrix, numBlocks, b);
stack(matrix, numBlocks, a, b);
}
else
{
clear(matrix, numBlocks, a);
stack(matrix, numBlocks, a, b);
}
}
else if (strcmp(cmd,"pile") == 0)
{
if (strcmp(action,"onto") == 0)
{
clear(matrix, numBlocks, b);
stack(matrix, numBlocks, a, b);
}
else
stack(matrix, numBlocks, a, b);

}

display(matrix, numBlocks);


}

return 0;
}
/* @END_OF_SOURCE_CODE */
[/c]

Anyone have a clue as to what I am doing wrong here? Any help would be most appreciated. I mostly just want to rule out the possibility that I am submitting the code incorrectly or something of that nature.

[Adrian Kuegel]

First I would use while(fgets(...)) instead of while(!feof(stdin)), because as far as I know feof(stdin) is true after reading EOF, and you should use it after a reading operation, not before it.
Then there is nothing said that you should display the piles after each successful command, only after the quit.
And your clear function is not correct, you should move the blocks on top of the original pile, not at first position (you know there can already be some block).
There can be other mistakes, but I have not looked long on your code.

[Frank]

Hi everybody, I just started solving the problems at ACM, but I think I found something wrong in the problem. in the "pile over" part it says:

pile a over b

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

and the sample input is :

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

I think the output to this point should be:

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

with block 6 on stack 1 instead of stack 5, because when you ask "pile 8 over 6" both of the blocks are on stack 1, so blocks 8 and 7 should be put on top of block 6.

What do you guys think?

Thanks,

Frank

[Adrian Kuegel]

There are commands that are invalid, this is one of them. In the problem description it is said that you should ignore them.

[Frank]

Thanks, I forgot that last comment.

Frank

[tabo]

Hello,

I dont quite understand the wording of the commands, for example:

* move a onto b

where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

this is what i think they are saying, please correct me if i am wrong...

0:
1: 1 2
2:
3: 3 5
4: 4
5:
6: 6

move 3 onto 1

0:
1: 1 3 5 2
2:
3:
4: 4
5:
6: 6

[hank]

* move a onto b

where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

(read it carefully.)

You have to return any blocks that are stacked on top of blocks a and b
to their initial positions.

Code: Select all

0: 
1: 1 2 
2: 
3: 3 5 
4: 4 
5: 
6: 6 

move 3 onto 1 

0: 
1: 1 3 
2: 2
3: 
4: 4 
5: 5
6: 6

[James]

0:
1:1 2
2:3
3:4 5 7
4:
5:
6:6
7:
After execute command "move 3 onto 1"
like follows step?
0:
1:1
2:3 2 or 2 3 ?
3:4 5
4:
5:
6:6
7:7
then
0:
1:1 4 5 or 1 5 4 ?
2:3 2 or 2 3
3:
4:
5:
6:6
7:7
===============================================
what 's effect of "move a over b" and "pile a onto b"?I don't know how to explain?
0:
1:1 2
2:3
3:4 5 7
4:
5:
6:6
7:
After command "move 3 over 6",what's result?
After command "pile 3 onto 6",what's result?
Thanks!

[cyfra]

Hi!

Here are answers for your questions :

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

After this command there is :
1:1 3
2:2
3:4 5 7
4:
5:
6:6
7:

===============================================
what 's effect of "move a over b" and "pile a onto b"?I don't know how to explain?
0:
1:1 2
2:3
3:4 5 7
4:
5:
6:6
7:
After command "move 3 over 6",what's result?
After command "pile 3 onto 6",what's result?

After move 3 over 6 there is :
0:
1:1 2
2:
3:4 5 7
4:
5:
6:6 3
7:

And after pile 3 onto 6 :

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

I hope it will help you ..

Good Luck

BTW.

You should move BLOCKS not positions !!

[James]

Hi!cyfra!I don't completely understand follows.I try to explain,then please help me to correct them.Thanks.
----------------------------------------------------------------------------------
move a onto b
where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions

Code: Select all

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
2:3
3:5
4:
5:
6:6
7:7
step 1:stacked on top of blocks 4 and 1 to their initial positions,so 7 and 6 will return to their initial positions.
step 2:puts block 4 onto block 1

===============================================
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.

Code: Select all

1:1 2 6
2:3 
3:4 5 7 
4: 
5: 
6:
7: 
After execute command "move 4 over 1" 
1:1 2 4
2:3
3:5
4:
5:
6:6
7:7
step 1:stacked on top of blocks 4 and 1 to their initial positions,so 7 and 6 will return to their initial positions.
step 2:puts block 4 onto the top of the stack containing block 1 

===============================================
pile a onto b
where a and b are block numbers, 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.

Code: Select all

1:1 2 6
2: 
3:3 4 5 7 
4: 
5: 
6:
7: 
After execute command "pile 4 onto 1" 
1:1 4 5 2  
2:
3:3 
4:
5:
6:6
7:7
step 1:All blocks on top of block 1 are moved to their initial positions,so 7 and 6 are moved to their initial positions.
step 2: The blocks stacked above block 4 retain their order when moved.

Could you please help me to modify?Thanks!

[23756AW]

Don't forget that if the blocks ocurr in the same stack that you ignore that command.

[HKcow]

I have got run time error, Could anyone help me to check for it?
I can run it on my system with all the test cases i made.
[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];
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]

[HellMind]

I dont understand nothing i need a graphical explication or something in spanish

[Adil]

hello there. didn't fine why your prog got runtime-error. but your prog isn't correct any way. test this input:

Code: Select all

10
move 9 over 9
move 8 over 9
move 7 over 9
move 6 onto 7
move 3 over 8
move 0 onto 8
move 2 over 13
move 2 over 10
move 4 over 7
move 6 over 7
move 1 onto 12
move 1 over 9
quit

fix the prog so that it gives correct output. and you'll see it won't get RE (let's hope so)

[bluemiles]

i got the right answer for the sample input.but the judge replied wa.
i'm confused by some topics focused on 101.
in my opinion ,you can't reach such a situation:
0:1
1:2
2:
3:3
.....

but this is ok:
0:0 1 2
1:
2:
3:
...

or :
0:
1:1 0 2
2:
3:3
...


i mean that no block can be in position 0 without block 0 in its initial position.
could anyone explain this to me?
or plz have a look at my source code or test it.

[cpp]#include<iostream>
#include<string>

using namespace std;

int count[26],state[26][25],pos[26][2];

void mov(int i,int j)
{
state[pos[0]][pos[1]]=-1;
count[pos[0]]--;
state[j][count[j]]=i;
pos[0]=j;
pos[1]=count[j];
count[j]++;
}

void init()
{
for(int i=0;i<26;i++)
{
count=1;
for(int j=0;j<25;j++)
{
state[j]=-1;
}
state[0]=i;
pos[0]=i;
pos[1]=0;
}
count[25]=0;
}

int main()
{
string command,mode;
int source,dest;
int i,j,n;
init();
cin>>n;
cin>>command;
while(!(command=="quit"))
{
cin>>source>>mode>>dest;
if(pos[source][0]==pos[dest][0])
goto end;
if(command=="move")
{

for(i=count[pos[source][0]]-1;i>pos[source][1];i--)
mov(state[pos[source][0]][i],state[pos[source][0]][i]);
if(mode=="over")
mov(source,pos[dest][0]);
else if(mode=="onto")
{
for(i=count[pos[dest][0]]-1;i>pos[dest][1];i--)
mov(state[pos[dest][0]][i],state[pos[dest][0]][i]);
mov(source,pos[dest][0]);
}
}
else if(command=="pile")
{
for(i=count[pos[source][0]]-1;i>=pos[source][1];i--)
mov(state[pos[source][0]][i],25);
if(mode=="over")
{
for(i=count[25]-1;i>=0;i--)
mov(state[25][i],pos[dest][0]);
}
else if(mode=="onto")
{
for(i=count[pos[dest][0]]-1;i>pos[dest][1];i--)
mov(state[pos[dest][0]][i],state[pos[dest][0]][i]);
for(i=count[25]-1;i>=0;i--)
mov(state[25][i],pos[dest][0]);
}

}
end:
cin>>command;
}
for(i=0;i<n;i++)
{
cout<<i<<':';
for(j=0;j<count[i];j++)
{
cout<<' '<<state[i][j];
}
cout<<endl;
}
return 0;
}
[/cpp]