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

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Sat Jun 29, 2002 3:10 pm

Please help me out with this prob
My code is above this message

tam
New poster
Posts: 3
Joined: Tue Jul 02, 2002 7:05 am

Problem 101 - Wrong Answer

Post by tam » Tue Jul 02, 2002 7:08 am

i don't know why, I get the Wrong Answer........
Please hELp.....

[pascal]

program p101;
var
i,j,n:integer;
s:string;
p:array [0..25,0..25] of byte;
fpos,fh,tpos,th:integer;
ss,sss:string;
mf,mt:integer;
temp:integer;

procedure search(block:integer; var pos1,height:integer);
var i,j:integer;
begin

for i:=0 to n-1 do
for j:=1 to p[i,0] do
if (p[i,j] = block) then
begin
pos1:=i;
height:=j;
exit;
end;
height:=0;
pos1:=n;

end;

procedure analysis(s:string);
var i,v:integer;
s1:string;
begin

delete(s,1,pos(' ',s));
s1:=copy(s,1,pos(' ',s)-1);
val(s1,mf,i);
delete(s,1,pos(' ',s));
sss:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
val(s,mt,i);


end;

procedure output;
var i,j:integer;
begin
for i:=0 to n-1 do
begin
write(' ',i,':');
for j:=1 to p[i,0] do
write(' ',p[i,j]);
writeln;
end;

end;

begin

readln(n);
for i:=0 to 25 do
for j:=1 to 25 do
p[i,j]:=0;

for i:=0 to n-1 do
begin
p[i,1]:=i;
p[i,0]:=1;
end;

while not (eof(input)) do
begin
readln(s);
if (pos('quit',s) <> 0) then
break;

ss:=copy(s,1,4);
analysis(s);

if (mf >= n) or (mt >= n) then
continue;

search(mf,fpos,fh);
search(mt,tpos,th);

if (fpos >= n) or (tpos >= n) or (fh = 0) or (th = 0) then continue;
if (fpos = tpos) or (mf = mt) then continue;

if (ss = 'move') and (fh = p[fpos,0]) then
if (sss = 'onto') and (th = p[tpos,0]) then
begin
p[tpos,0]:=p[tpos,0] + 1;
p[tpos, p[tpos,0]]:=p[fpos, p[fpos,0]];
p[fpos,0]:=p[fpos,0] - 1;
end
else
if (sss = 'over') then
begin
p[tpos,0]:=p[tpos,0] + 1;
p[tpos, p[tpos,0]]:=p[fpos, p[fpos,0]];
p[fpos,0]:=p[fpos,0] - 1;
end;

if (ss = 'pile') then
if (sss = 'onto') and (th = p[tpos,0]) then
begin

temp:=1+( p[fpos,0] - fh);
for i:=1 to temp do
begin
p[tpos,0]:=p[tpos,0] + 1;
p[tpos, p[tpos,0]]:=p[fpos, fh+i-1];
p[fpos,0]:=p[fpos,0] - 1;
end;

end
else
if (sss = 'over') then
begin

temp:=1+( p[fpos,0] - fh);
for i:=1 to temp do
begin
p[tpos,0]:=p[tpos,0] + 1;
p[tpos, p[tpos,0]]:=p[fpos, fh+i-1];
p[fpos,0]:=p[fpos,0] - 1;
end;

end;

end;

output;


end.
[/pascal]

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Tue Jul 02, 2002 7:17 am

Have you searched and read the previous posts about problem 101? (There should be a lot)

I think the posts can help~

And could you please post your post in the thread about 101, as it's not a new topic.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Tue Jul 09, 2002 10:27 am

Hmm
Your program does nothing for the input which is in task description...

Try to change it :)

Good Luck :wink:

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Tue Jul 09, 2002 12:09 pm

plz explain...
i couln't undersatnd what you want to say..

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Tue Jul 09, 2002 12:20 pm

hmm...

I have copied your source then compiled it and then tested on the sample input...

Your program answer was:
0: 0
1: 1
...
and so on...

The same things happened to the other tests...

I don't know maybe it is my compilator failure but it also can be your program fault...

And what does your program give on your computer ??

Good Luck :wink:

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Tue Jul 09, 2002 12:43 pm

The prog question says
Sample Output

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

My prog also gives answer like that.... i can't see anything wrong with my output.

rhtiwari
New poster
Posts: 5
Joined: Thu Jul 11, 2002 10:59 am

Post by rhtiwari » Thu Jul 11, 2002 6:28 pm

In my opinion the whole confusion is because you are assuming that there can be other blocks in a position while the original block itself is not there.
For example blocks 7 and 8 can be in the position of block 3 while block 3 is at that instant in another position, say in the position of block 2.

However, if you think about it, then with the given starting condition and the given operations, the above scenario is just not possible. Removing the code for that scenario should help.

Slayer
New poster
Posts: 1
Joined: Tue Jul 09, 2002 9:02 pm
Location: Dublin
Contact:

Problem 101 input problems

Post by Slayer » Fri Jul 12, 2002 8:45 pm

Please help me!

I am currently working on the 101 problem and am having a problem with the C++ iostream function cin.getline().

I believe that its from not clearing the input stream, but I don't know how one goes about doing this.

I first enter in the number of blocks

[cpp]int size;
cin >> size;[/cpp]

and then later when I want to take in the instruction as a single string

[cpp]char op[80];
cin.getline(op, 80);[/cpp]

This will not let the user do anything at all, and the debugger will just skip the line altogether.

If it is the first input line in the program it appears to work, so the clearing/flushing the input stream should solve this. If someone would like to tell me how.
Please Help!

nariini
New poster
Posts: 4
Joined: Tue Jul 16, 2002 12:38 pm

problem 101 - compile error... help me..

Post by nariini » Tue Jul 16, 2002 1:05 pm

i received error message

***************************************
Here are the compiler error messages:

/tmp/cc9xBj1ymain.o: In function `main':
/tmp/ccpj56nDmain.i(.text+0x12): undefined reference to `_CL_4Main'
collect2: ld returned 1 exit status

***************************************

[/java]
import java.io.*;
import java.util.*;

class Prob_101_site
{

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[])
{
Prob_101_site myWork = new Prob_101_site();
myWork.Begin();
}

void Begin()
{
String line;
StringTokenizer idata;
int a, b, n;
int arr[][];
String op_1;
String op_2;
try
{
line = Prob_101_site.ReadLn(255);
idata = new StringTokenizer(line);
n = Integer.parseInt(idata.nextToken());
arr = new int[n][n];

/* initially array setting */
for (int i=0; i<=n-1; i++)
{
for (int j=0; j<=n-1; j++)
{
if (j==0) arr[j] = i;
else arr[j] = -1;
}
}
while ( (line = Prob_101_site.ReadLn(255)) != null)
{
idata = new StringTokenizer (line);
if( 1 == idata.countTokens()){
break;
} else{
op_1 = idata.nextToken();
a = Integer.parseInt (idata.nextToken());
op_2 = idata.nextToken();
b = Integer.parseInt (idata.nextToken());

int a_i = -1, a_j = -1, b_i = -1, b_j = -1, b_l = -1;

/* a, b&#51032; &#50948;&#52824; &#50508;&#50500;&#45236;&#44592; */
for (int j=0; j<=n-1; j++)
{
for (int i=0; i<=n-1; i++)
{
if (a == arr[j])
{
a_i = i;
a_j = j;
}
if (b == arr[j])
{
b_i = i;
b_j = j;
}
if (a_i != -1 && b_i != -1)
{
i = n;
j = n;
}
}
}//end for

// [&#52628;&#44032;]&#47564;&#50557; a&#50752; b&#44032; &#44057;&#51008; array&#50640; &#51080;&#51004;&#47732;.. &#50500;&#47924;&#44163;&#46020; &#50504;&#54616;&#44592;
if (a!=b && a_i!=b_i)
{

/* &#50672;&#49328; &#51333;&#47448;&#46384;&#46972; &#49688;&#54665;&#54616;&#44592; */
if (op_1.equals("move"))
{
for (int l=n-1; l>a_j; l--) //block a &#50948;&#51032; &#44163; &#51228;&#51088;&#47532;&#47196; &#50734;&#44592;&#44592;
{
if (arr[a_i][l] != -1)
{
arr[a_i][0] = arr[a_i][l];
arr[a_i][l] = -1;
}
} //end for
if (op_2.equals("onto")) //block b &#50948;&#51032; &#44163; &#51228;&#51088;&#47532;&#47196; &#50734;&#44592;&#44592;
{
for (int l=n-1; l>b_j; l--)
{
if (arr[b_i][l] != -1)
{
arr[b_i][0] = arr[b_i][l];
arr[b_i][l] = -1;
}
}
} //end if
for (int l=0; l<=n-1; l++) //block a&#47484; block b&#51032; &#50948;&#47196; &#50734;&#44592;&#44592;
{
if (arr[b_i][l] == -1)
{
arr[b_i][l] = arr[a_i][a_j];
arr[a_i][a_j] = -1;
}
}//end for
}//end if "move"

else if (op_1.equals("pile"))
{
if (op_2.equals("onto")) //block b &#50948;&#51032; &#44163; &#51228;&#51088;&#47532;&#47196; &#50734;&#44592;&#44592;
{
for (int l=n-1; l>b_j; l--)
{
if (arr[b_i][l] != -1)
{
arr[b_i][0] = arr[b_i][l];
arr[b_i][l] = -1;
}
}
} //end if
for (int l=1; l<=n-1; l++) //block b&#50948;&#47484; &#44160;&#49353;
{
if (arr[b_i][l] == -1) // block b&#51032; null&#51064; &#44275;&#51012; &#52286;&#50520;&#51004;&#47732;,
{
b_l = l;
break;
}
} //end for

for (int m=a_j; m<=n-1; m++)
{
if (arr[a_i][m] != -1)
{
arr[b_i][b_l] = arr[a_i][m];
arr[a_i][m] = -1;
b_l++;
}
else if (arr[a_i][m] == -1) //&#45796; &#50734;&#44220;&#51020; &#45208;&#44032;&#44592;
{
m = n;
}
}// end for
}// end else if "pile"
} //end if
} //end else
}//end while
for(int i = 0; i < n; i++){
System.out.print(i+": ");
for(int j = 0; j < n; j++){
if(arr[j] != -1)
System.out.print(" "+arr[j]);
}
System.out.println();
}
// out.close();

}catch(Exception e) {System.out.println("error:" + e);}
}

}

************************************************************

i don't know what this message say.

please, help me..

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

101

Post by htl » Tue Jul 16, 2002 6:04 pm

This problem should be a easy one. But I alway got RE. I rewrite it several times and cannot get AC. Could someone help me?
[c]
#include<stdio.h>
#include<string.h>
int block[25][25],top[25],pos[25];
void unload(int);
void main(void)
{
int n,x,a,b,temp[25],count,t,y;
char com1[5],com2[5];
scanf("%d",&n);
for(x=0;x<n;x++)
block[x][0]=pos[x]=x,top[x]=0;
while(1)
{
scanf("%s",com1);
if(strcmp(com1,"quit")==0)
break;
scanf("%d",&a);
scanf("%s",com2);
scanf("%d",&b);
if(a==b || pos[a]==pos)
continue;
if(strcmp(com2,"onto")==0)
unload(b);
if(strcmp(com1,"move")==0)
{
unload(a);
t=block[pos[a]][top[a]--];
block[pos][++top[pos]]=t;
pos[a]=pos;
}
if(strcmp(com1,"pile")==0)
{
for(x=top[pos[a]],count=0;x>=0;x--)
if(block[pos[a]][x]!=a)
{
temp[count++]=block[pos[a]][x];
top[pos[a]]--;
}
else if(block[pos[a]][x]==a)
{
temp[count++]=block[pos[a]][x];
top[pos[a]]--;
break;
}
for(x=count-1;x>=0;x--)
{
t=temp[x];
block[pos][++top[pos]]=t;
pos[t]=pos;
}
}
}
for(x=0;x<n;x++)
{
printf("%d:",x);
if(top[x]>=0)
for(y=0;y<=top[x];y++)
printf(" %d",block[x][y]);
printf("\n");
}
}
void unload(int i)
{
int x,temp[25],count,t;
for(x=top[pos],count=0;x>=0;x--)
if(block[pos][x]!=i)
{
temp[count++]=block[pos][x];
top[pos]--;
}
else if(block[pos][x]==i)
break;
for(x=0;x<count;x++)
{
t=temp[x];
block[t][++top[t]]=t;
pos[t]=t;
}
}
[/c]

nariini
New poster
Posts: 4
Joined: Tue Jul 16, 2002 12:38 pm

[problem 101] i don't know what means this error message

Post by nariini » Thu Jul 18, 2002 3:34 am

i received error message

***************************************
Here are the compiler error messages:

/tmp/cc9xBj1ymain.o: In function `main':
/tmp/ccpj56nDmain.i(.text+0x12): undefined reference to `_CL_4Main'
collect2: ld returned 1 exit status

***************************************

[/java]
import java.io.*;
import java.util.*;

class Prob_101_site
{

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[])
{
Prob_101_site myWork = new Prob_101_site();
myWork.Begin();
}

void Begin()
{
String line;
StringTokenizer idata;
int a, b, n;
int arr[][];
String op_1;
String op_2;
try
{
line = Prob_101_site.ReadLn(255);
idata = new StringTokenizer(line);
n = Integer.parseInt(idata.nextToken());
arr = new int[n][n];

/* initially array setting */
for (int i=0; i<=n-1; i++)
{
for (int j=0; j<=n-1; j++)
{
if (j==0) arr[j] = i;
else arr[j] = -1;
}
}
while ( (line = Prob_101_site.ReadLn(255)) != null)
{
idata = new StringTokenizer (line);
if( 1 == idata.countTokens()){
break;
} else{
op_1 = idata.nextToken();
a = Integer.parseInt (idata.nextToken());
op_2 = idata.nextToken();
b = Integer.parseInt (idata.nextToken());

int a_i = -1, a_j = -1, b_i = -1, b_j = -1, b_l = -1;

for (int j=0; j<=n-1; j++)
{
for (int i=0; i<=n-1; i++)
{
if (a == arr[j])
{
a_i = i;
a_j = j;
}
if (b == arr[j])
{
b_i = i;
b_j = j;
}
if (a_i != -1 && b_i != -1)
{
i = n;
j = n;
}
}
}//end for


if (a!=b && a_i!=b_i)
{

if (op_1.equals("move"))
{
for (int l=n-1; l>a_j; l--)
{
if (arr[a_i][l] != -1)
{
arr[a_i][0] = arr[a_i][l];
arr[a_i][l] = -1;
}
} //end for
if (op_2.equals("onto"))
{
for (int l=n-1; l>b_j; l--)
{
if (arr[b_i][l] != -1)
{
arr[b_i][0] = arr[b_i][l];
arr[b_i][l] = -1;
}
}
} //end if
for (int l=0; l<=n-1; l++)
{
if (arr[b_i][l] == -1)
{
arr[b_i][l] = arr[a_i][a_j];
arr[a_i][a_j] = -1;
}
}//end for
}//end if "move"

else if (op_1.equals("pile"))
{
if (op_2.equals("onto"))
{
for (int l=n-1; l>b_j; l--)
{
if (arr[b_i][l] != -1)
{
arr[b_i][0] = arr[b_i][l];
arr[b_i][l] = -1;
}
}
} //end if
for (int l=1; l<=n-1; l++)
{
if (arr[b_i][l] == -1)
{
b_l = l;
break;
}
} //end for

for (int m=a_j; m<=n-1; m++)
{
if (arr[a_i][m] != -1)
{
arr[b_i][b_l] = arr[a_i][m];
arr[a_i][m] = -1;
b_l++;
}
else if (arr[a_i][m] == -1)
{
m = n;
}
}// end for
}// end else if "pile"
} //end if
} //end else
}//end while
for(int i = 0; i < n; i++){
System.out.print(i+": ");
for(int j = 0; j < n; j++){
if(arr[j] != -1)
System.out.print(" "+arr[j]);
}
System.out.println();
}
// out.close();

}catch(Exception e) {System.out.println("error:" + e);}
}

}

************************************************************

i don't know what this message say.

please, help me..

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Thu Jul 18, 2002 6:51 am

The class name MUST be Main ... :o

Check out this page: http://acm.uva.es/problemset/howtows.html#java and http://acm.uva.es/problemset/java.html

nariini
New poster
Posts: 4
Joined: Tue Jul 16, 2002 12:38 pm

thanx

Post by nariini » Thu Jul 18, 2002 10:23 am

thanx :oops:

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Wed Jul 24, 2002 3:09 pm

I couldn't underwstand why i should i think the way tiwari ji has told me.....
My prog is acting acoording to the input.....
Even if what tiwari ji has told is true i don't see where my prog contradicts his argument.......
Can any one give me a sample input where my prog fails to run.....
i have already given my prog in this thread....

Post Reply

Return to “Volume 1 (100-199)”