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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Your code is too big to find a single mistake in it. It is much more complex than necessary. It looks much too slow as well.
All operations can be coded in O(h), where h it the height of the stack the operation is done on.
As for the example input you asked for, try to search the forum for it. There are many posts about problem 101.
El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto »

My app got accepted. I included part of my app below (the functions to handle the commands).

[cpp]
// 1. Any blocks on top of the source block are restored to their original stack.
// 2. Any blocks on top of the destination block are restored to their original stack.
// 3. Move the source block on top of the destination block
void CBlockStack::Cmd_MoveOnto(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the source block to their original stack
RestoreBlocksToOriginalStack(i16SrcStack, i16SrcPos + 1);

// Restore any blocks on top of the destination block to their original stack
RestoreBlocksToOriginalStack(i16DstStack, i16DstPos + 1);

// Move the source block on top of the destination block
m_ppi16Blocks[i16DstStack][i16DstPos+1] = i16SrcBlock;
m_ppi16Blocks[i16SrcStack][i16SrcPos] = -1;
}
}
}


//------------------------------------------------------------------------------------


// 1. Any blocks on top of the source block are restored to their original stack.
// 2. Move the source block to the top of the destination stack
void CBlockStack::Cmd_MoveOver(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the source block to their original stack
RestoreBlocksToOriginalStack(i16SrcStack, i16SrcPos + 1);

// Move the source block on top of the destination stack
m_ppi16Blocks[i16DstStack][GetTopOfStack(i16DstStack)+1] = i16SrcBlock;
m_ppi16Blocks[i16SrcStack][i16SrcPos] = -1;
}
}
}


//------------------------------------------------------------------------------------


// 1. Any blocks on top of the destination block are restored to their original stack.
// 2. The source block and any blocks above it are picked up.
// 3. The picked up blocks are placed on top of the stack of the destination block
void CBlockStack::Cmd_PileOnto(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the destination block to their original stack
RestoreBlocksToOriginalStack(i16DstStack, i16DstPos + 1);

// The destination block is now the top block of its stack, so we can pile the source block over the destination block
Cmd_PileOver(i16SrcBlock, i16DstBlock);
}
}
}


//------------------------------------------------------------------------------------


// 1. The source block and any blocks above it are picked up.
// 2. The picked up blocks are placed on top of the stack of the destination block.
void CBlockStack::Cmd_PileOver(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos, i16BlocksToMove;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Get the amount of blocks to move
i16BlocksToMove = GetTopOfStack(i16SrcStack) - i16SrcPos + 1;

// Copy the pile to the top of the destination stack
memcpy(&m_ppi16Blocks[i16DstStack][GetTopOfStack(i16DstStack)+1], &m_ppi16Blocks[i16SrcStack][i16SrcPos], i16BlocksToMove * sizeof(int16));

// Remove the pile from the source stack
memset(&m_ppi16Blocks[i16SrcStack][i16SrcPos], -1, i16BlocksToMove * sizeof(int16));
}
}
}
[/cpp]

If you need more help, let me know.
El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto »

In case anyone wants to test this problem, I wrote a test case generator for my own app (helped me to get accepted):

[cpp]
#define TOT_ELEMS 20
#define TOT_ACTIONs 25

FILE *pfDst;

if(pfDst = fopen("Input.txt", "w"))
{
fprintf(pfDst, "%i\n", TOT_ELEMS);
srand((unsigned int)time(NULL));
for(int32 i32=0;i32<TOT_ACTIONS;i32++)
{
// Create a random action
fprintf(pfDst,
"%s %i %s %i\n",
rand() % 2 ? "move" : "pile",
rand() % TOT_ELEMS,
rand() % 2 ? "onto" : "over",
rand() % TOT_ELEMS);
}
fprintf(pfDst, "quit");
fclose(pfDst);
}
[/cpp]
Ruslan Shevelyov
New poster
Posts: 15
Joined: Fri Aug 08, 2003 8:13 pm
Location: Russia, Moscow
Contact:

Post by Ruslan Shevelyov »

Those char act1[4],act2[4] look suspiciously. Looks like you forgot to reserve space for trailing zero.
On my machine your program just leaves these boxes as is.
www.Find-a-Drug.org distributed computing project
palespower
New poster
Posts: 6
Joined: Fri Aug 15, 2003 9:12 am

101 Runtime Error ... help

Post by palespower »

Plz I've submit my program on the blocks problem and I'm getting this message....
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.006 seconds.
Can any body help me????? :-?
InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Re: ACM 101

Post by InOutMoTo »

0:
1:1 2
2:3
3:4 5 7
4:
5:
6:6
7:
I don't think it will happen.
"3" cannot be the first block in No.2 area.
"4" cannot be 3's first place , either.

Think of the constructions and u will found that :lol:

I got AC without considering special cases.

It's not too difficult.

GoOd LuCk. :wink:
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Be sure that all your pointers are set correctly. Check twice your writing/reading from arrays, maby some indexes are inproper, the same for the iterators. This kind of error is quite easy to find, you shouldn't have any problem.
Ji-Yung
New poster
Posts: 1
Joined: Thu Aug 21, 2003 12:47 pm

WA in 101 help

Post by Ji-Yung »

Though I've tried a lot of examples
I still can't find what's wrong in my code
Would somebody likes to help me?


[c]
/* @JUDGE_ID: 33940RW 101 C "101" */
#include<string.h>
#include<stdio.h>
typedef enum{MOVE_ONTO,MOVE_OVER,PILE_ONTO,PILE_OVER} ACTION;

char blocks[25][26];
int n_blocks =0;
char indexs[25][2];
char tempb[26];
char tempa[26];

void move(char a,char b,ACTION act)
{
int i =1;
int Xa=indexs[a][0];
int Ya=indexs[a][1];
int Xb=indexs[0];
int Yb=indexs[1];
int pile =1;

memcpy(tempb,&blocks[Xb],26);
memcpy(tempa,&blocks[Xa],26);
if (act==PILE_ONTO||act==PILE_OVER)
{
printf("called");
pile=tempa[0]-Ya+1;

if (act==PILE_OVER)
{
memcpy(&blocks[Xb][tempb[0]+1],&tempa[Ya],25-tempb[0]);
}
else
{
memcpy(&blocks[Xb][Yb+1],&tempa[Ya],25-Yb);
memcpy(&blocks[Xb][Yb+1+pile],&tempb[Yb+1],25-Yb-pile);
}

memset(&blocks[Xa][Ya],26,pile);

}else if (act==MOVE_OVER)
{
blocks[Xb][tempb[0]+1]=a;
memcpy(&blocks[Xa][Ya],&tempa[Ya+1], tempa[0] - Ya+1);

}else
{
blocks[Xb][Yb+1]=a;
memcpy(&blocks[Xb][Yb+2],&tempb[Yb+1],tempb[0]-Yb);
memcpy(&blocks[Xa][Ya],&tempa[Ya+1] , tempa[0] - Ya+1);
}

while (blocks[Xb][Yb+i]<26)
{
indexs[blocks[Xb][Yb+i]][1]=Yb +i;
indexs[blocks[Xb][Yb+i]][0]=Xb ;
i++;
}

if (act==MOVE_ONTO||act==MOVE_OVER)
{
i=1;
while (tempa[Ya+i]<26)
{
indexs[tempa[Ya+i]][1] --;
i++;
}
}

blocks[Xb][0]+=pile;
blocks[Xa][0]-=pile;

}

void output()
{
int i=0;
int j=0;

while( n_blocks>i)
{
printf("%d:",i);
for(j=1;j<25 && blocks[j]!=26;j++)
{
printf(" %d",blocks[j]);
}
i++;
printf("\n");
}
}


int main(int argc, char *argv[])
{

char cmd1[5];
char cmd2[5];
int a = 0;
int b = 0;
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
freopen("output","w", stdout);
#endif

scanf("%d",&n_blocks);
memset(blocks,26,sizeof(blocks));

for(;a<n_blocks;a++ )
{
blocks[a][0] = 1;
blocks[a][1] = a;
indexs[a][0] = a;
indexs[a][1] = 1;
}

while (scanf("%s %d %s %d",&cmd1,&a,&cmd2,&b)==4)
{

if (indexs[0]!= indexs[a][0])
{

if (cmd1[0]=='m' )
{
if (cmd2[2]=='e')
{
move(a,b,MOVE_OVER);
}else{
move(a,b,MOVE_ONTO);
}
}else if (cmd2[2]=='t')
{
move(a,b,PILE_ONTO);
}else if (cmd2[2]=='e')
{
move(a,b,PILE_OVER);
}
}
}
output();
return 0;
}

[/c]

Sorry because I am a newbie
I 've re-typesetting my codes
Last edited by Ji-Yung on Thu Aug 21, 2003 1:38 pm, edited 1 time in total.
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

Your code is hard to read. Try editing it and adding tags to format it.

For example, stick [ cpp ] and [ /cpp ] in your message around your code.
calinous
New poster
Posts: 3
Joined: Wed Sep 24, 2003 10:33 am
Contact:

Post by calinous »

I have the same problem. And it is not related to pointers or anything else - the code run flawlessly on both Visual C++6 and djgpp, ver 3.31 C compiler.
I assume it is related to the C compiler version of the jury - or maybe the runtime system
calinous
New poster
Posts: 3
Joined: Wed Sep 24, 2003 10:33 am
Contact:

Post by calinous »

You can use freopen - works at least in Visual C++ 6
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

No. Which version of MS Windows do you use? I bet it's none of the NT family. Am I right?
calinous
New poster
Posts: 3
Joined: Wed Sep 24, 2003 10:33 am
Contact:

Post by calinous »

You just lost the bet, I am using Windows 2000.

But I was able to solve the runtime error - now I get WA. I assume my program was accessing bad indexes in an array (like a[-1][0], let's say). I don't know where the error is, but this is much better.
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Strange - Win2k should have noticed that you tried to access unreserved, protected memory. In such cases my Win2k dumps the core.

Anyway, the problem definitely was related to pointers ;-)
Six of Three
New poster
Posts: 5
Joined: Mon Sep 29, 2003 8:59 am
Location: Germany: Jena
Contact:

Re: 101 output format

Post by Six of Three »

Archer wrote:[c]printf("%2i:", pos);[/c]
This is similar to the Pascal code
[pascal]write(pos:2,':');[/pascal]
which reproduces the sample output with leading blanks in front of 0-9, but generates a presentation error. The correct output should be achieved by
Archer wrote:[c]printf("%i:", pos);[/c]
or the Pascal version
[pascal]write(pos:1,':');[/pascal]

Such a trap door in the second problem... looks like if somebody wanted to tell us not to believe in sample outputs :wink:
We Are The BORG. You Will Be Assimilated. Resistance Is Futile.
Post Reply

Return to “Volume 1 (100-199)”