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

Post Reply
Jubba
New poster
Posts: 1
Joined: Fri Aug 23, 2002 7:40 am

p101 - WA madness - HELP!

Post by Jubba » Fri Aug 23, 2002 8:02 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Aug 23, 2002 11:59 am

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
New poster
Posts: 2
Joined: Wed Sep 18, 2002 4:44 pm
Location: Brazil

possible bug on 101

Post by Frank » Wed Sep 18, 2002 5:01 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 18, 2002 6:26 pm

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

Frank
New poster
Posts: 2
Joined: Wed Sep 18, 2002 4:44 pm
Location: Brazil

thanks

Post by Frank » Wed Sep 18, 2002 7:35 pm

Thanks, I forgot that last comment.

Frank

tabo
New poster
Posts: 2
Joined: Fri Sep 20, 2002 7:05 pm
Contact:

Problem 101 question

Post by tabo » Fri Sep 20, 2002 8:49 pm

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Sat Sep 21, 2002 4:48 am

* 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
New poster
Posts: 2
Joined: Wed Sep 25, 2002 12:56 pm

ACM 101

Post by James » Wed Sep 25, 2002 1:35 pm

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Re: ACM 101

Post by cyfra » Wed Sep 25, 2002 2:29 pm

Hi!

Here are answers for your questions :
James wrote: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:
James wrote: ===============================================
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 :wink:

BTW.

You should move BLOCKS not positions !!

James
New poster
Posts: 2
Joined: Wed Sep 25, 2002 12:56 pm

Post by James » Thu Sep 26, 2002 4:05 pm

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
New poster
Posts: 5
Joined: Mon Sep 30, 2002 1:00 am

Friendly reminder

Post by 23756AW » Mon Sep 30, 2002 1:02 am

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

HKcow
New poster
Posts: 10
Joined: Fri Aug 30, 2002 2:34 pm

101, Runtime Error

Post by HKcow » Sat Oct 05, 2002 2:12 pm

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
New poster
Posts: 1
Joined: Fri Oct 04, 2002 9:04 pm
Location: Rosario, Argentina
Contact:

Post by HellMind » Sat Oct 05, 2002 11:33 pm

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

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Sun Oct 06, 2002 12:22 pm

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) :wink:

bluemiles
New poster
Posts: 1
Joined: Mon Oct 07, 2002 6:48 am
Location: beijing china

101

Post by bluemiles » Mon Oct 07, 2002 7:26 am

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.
:o
[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]

Post Reply

Return to “Volume 1 (100-199)”