101 - The Blocks Problem

[rdinix]

Hi, Archer
I think your code is not dealing with cases such as a<0 or b<0

[Archer]

well I added a a<0 or b<0 check to my functions, but still it's saying wrong answer

[tp]

My ACd code uses the second:
[c]printf("%i:", pos);[/c]

[rdinix]

And >25?

[Moni]

But I think this will not help me in escape from RTE !!!

[Adil]

hello there moni.

read the problem statement VERY carefully. it says

All illegal commands should be ignored and should have no affect on the configuration of blocks.

and then

There will be no syntactically incorrect commands.

it's a good idea to assume that the judge will give illegal commands, which might include commands like

move 112 over 231

in such a case, your program would most likely crash in the "check" function. fix that, and hopefully you'll get rid of the RTE.

hope this helps. let me know what happens.

[Moni]

Hai! I havn't checked yet, but I know for your input as there is no space (112 or 231)like that :

#define ROW 100
#define COL 100

Of course it falls !!!

[ec3_limz]

Got WA for this code, what's wrong?

BTW, add() adds a block to another stack, and remove() returns a block to its original stack.

Please help me...

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

int blocks, loc[25], pos[25][25], next[25];

void add(int block, int to) {
loc[block] = to * 100 + next[to];
pos[to][next[to]] = block;
next[to]++;
}

void remove(int start, int end) {
int i;

for (i = start % 100; i < end % 100; i++) {
add(pos[start / 100], pos[start / 100]);
pos[start / 100] = -1;
}
next[start / 100] = start % 100;
}

int main() {
char cmd[5], prep[5];
int block1, block2, temp;
int i, j;

scanf("%d", &blocks);
for (i = 0; i < blocks; i++) {
loc = i * 100;
next = 1;
pos[0] = i;
for (j = 1; j < blocks; j++)
pos[j] = -1;
}

while (true) {
scanf("%s", &cmd);
if (strcmp(cmd, "quit") == 0)
break;

scanf("%d%s%d", &block1, &prep, &block2);
if (loc[block1] / 100 == loc[block2] / 100)
continue;

if (strcmp(cmd, "move") == 0) {
if (strcmp(prep, "onto") == 0) {
remove(loc[block1], (loc[block1] / 100) * 100 + next[loc[block1] / 100]);
remove(loc[block2] + 1, (loc[block2] / 100) * 100 + next[loc[block2] / 100]);
add(block1, loc[block2] / 100);
}
else if (strcmp(prep, "over") == 0) {
remove(loc[block1], (loc[block1] / 100) * 100 + next[loc[block1] / 100]);
add(block1, loc[block2] / 100);
}
}
else if (strcmp(cmd, "pile") == 0) {
if (strcmp(prep, "onto") == 0) {
temp = loc[block1];
remove(loc[block2] + 1, (loc[block2] / 100) * 100 + next[loc[block2] / 100]);
for (i = loc[block1]; i % 100 < next[i / 100]; i++)
add(pos[i / 100][i % 100], loc[block2] / 100);
for (i = temp; i % 100 < next[i / 100]; i++)
pos[i / 100][i % 100] = -1;
next[temp / 100] = temp % 100;
}
else if (strcmp(prep, "over") == 0) {
temp = loc[block1];
for (i = loc[block1]; i % 100 < next[i / 100]; i++)
add(pos[i / 100][i % 100], loc[block2] / 100);
for (i = temp; i % 100 < next[i / 100]; i++)
pos[i / 100][i % 100] = -1;
next[temp / 100] = temp % 100;
}
}
}

for (i = 0; i < blocks; i++) {
printf("%d:", i);
for (j = 0; j < next; j++)
printf(" %d", pos[j]);
printf("\n");
}

return 0;
}[/cpp]

[Archer]

yeah, still... can the c = getchar(); after the scanf("%d", &worldsize); be a problem? maybe use fflush(stdin) instead? hmm...

[rdinix]

Well, I think you got it!
getchar() is not really necessary!
scanf() can do the job for you!
I would also recomend you to test your program with a command set like:

25
pile -9 onto -333
move 75 over 75
move 20 onto 25
quit

Good Luck!!!

[25258FM]

why?
[c]/* @JUDGE_ID: 25258FM 101 C "AI??" */

#include <stdio.h>
int block[25][25];
char input[100];
char cur_char,dummy;
void CutCommand();
int max,command1;
int command2;
int com_num1,com_num2;
int timeofcleantop;
void progress11();
void progress12();
void progress22();
void progress21();
int GetNumberOfTime(int);
void cleantop(int num);
int cleanx,cleany,movetox,movetoy;
void getposition();

int main(void)
{ int i=0,j;
scanf("%d", &max);
scanf("%c",&dummy);
for (i=0;i<max;i++)
for (j=0;j<max;j++)
if (i==0)
block[0][j]=j;
else
block[j]=-1;

do
{

for (j=0;j<100;j++)
input[j]='*';
i=0;
while ((cur_char=getchar())!=10)
{
input=cur_char;
i++;
}

CutCommand();
if ((com_num1!=com_num2)&&(com_num1>=0)&&(com_num2>=0)&&(com_num1<max)&&(com_num2<max))
{
if ((command1==1)&&(command2==1))
progress11();
if ((command1==1)&&(command2==2))
progress12();
if ((command1==2)&&(command2==1))
progress21();
if ((command1==2)&&(command2==2))
progress22();
}

}while (input[0]!='q');

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

if (block[j]!=-1)
printf(" %d",block[j]);
}
printf("\n");
}


}

void CutCommand()
{
int k=5,yes=0;


if ((input[0]=='m')&&(input[1]=='o')&&(input[2]=='v')&&(input[3]=='e'))
command1=1;
if ((input[0]=='p')&&(input[1]=='i')&&(input[2]=='l')&&(input[3]=='e'))
command1=2;

while (input[k]!=' ')
k++;
if (k==7)
{
yes=1;
com_num1=(input[5]-48)*10+(input[6]-48);
}
if (k==6)
com_num1=(input[5]-48);


for (k=7;k<=8;k++)
{
if ((input[k]=='o')&&(input[k+1]=='n')&&(input[k+2]=='t')&&(input[k+3]=='o'))
command2=1;
if ((input[k]=='o')&&(input[k+1]=='v')&&(input[k+2]=='e')&&(input[k+3]=='r'))
command2=2;
}

if ((yes==1)&&(input[14]=='*'))
com_num2=input[13]-48;

if ((yes==1)&&(input[14]!='*'))
com_num2=(input[13]-48)*10+input[14]-48;


if ((yes==0)&&(input[13]!='*'))
com_num2=(input[12]-48)*10+input[13]-48;

if ((yes==0)&&(input[13]=='*'))
com_num2=input[12]-48;


}




void cleantop(int num)
{
int i=0,j=0,cleanx=0,cleany=0,k=0,number=0;

for (i=0;i<max;i++)
for (j=0;j<max;j++)
if (block[j]==num)
{cleanx=i;cleany=j;}


for (k=cleanx;k<max;k++)
if ((block[k+1][cleany]==-1)&&(block[k][cleany]!=num))
{
number=block[k][cleany];
for (i=0;i<max;i++)
if (block[number]==-1)
{
block[number]=block[k][cleany];
break;
}
block[k][cleany]=-1;
}

}

int GetNumberOfTime(int num)
{
int i=0,j=0,cleanx=0,cleany=0,numberoftime=0;
for (i=0;i<max;i++)
for (j=0;j<max;j++)
if (block[j]==num)
{cleanx=i;cleany=j;}
for (i=cleanx+1;i<max;i++)
if (block[cleany]!=-1)
numberoftime++;

return numberoftime;
}



void doallcleantop(int num)
{
timeofcleantop=GetNumberOfTime(num);
while (timeofcleantop){
cleantop(num);
timeofcleantop--;
}
}
void progress11()
{
doallcleantop(com_num1);
doallcleantop(com_num2);
getposition();
block[movetox+1][movetoy]=block[cleanx][cleany];
block[cleanx][cleany]=-1;
}


void progress12()
{
int i;
doallcleantop(com_num1);
getposition();
for (i=movetox+1;i<max;i++)
if (block[movetoy]==-1)
break;
block[i][movetoy]=block[cleanx][cleany];
block[cleanx][cleany]=-1;
}

void progress21()
{
int i,j,k;
doallcleantop(com_num2);
getposition();
for (i=cleanx+1;i<max;i++)
if (block[i][cleany]==-1)
break;
for (k=cleanx,j=movetox+1;k<i;k++,j++)
{
block[j][movetoy]=block[k][cleany];
block[k][cleany]=-1;
}
}

void progress22()
{
int i,j,k,l;
getposition();
for (i=movetox+1;i<max;i++)
if (block[i][movetoy]==-1)
break;
for (l=cleanx+1;l<max;l++)
if (block[l][cleany]==-1)
break;
for (k=cleanx,j=i;k<l;k++,j++)
{
block[j][movetoy]=block[k][cleany];
block[k][cleany]=-1;
}
}

void getposition()
{
int i,j;
cleanx=0;cleany=0;
for(i=0;i<max;i++)
for(j=0;j<max;j++)
if (block[i][j]==com_num1)
{cleanx=i;cleany=j;}

for(i=0;i<max;i++)
for(j=0;j<max;j++)
if (block[i][j]==com_num2)
{movetox=i;movetoy=j;}
}[/c]

[Olorin]

Well, I'll say !
Hate to post a solution that is nothing special, but I am getting the "Memory Limit Exceeded" reply form the judge, and I sure am wondering where the leak might come from. So, please take a look and let me know what you think. Thanks in advance (sorry if the indentation looks bad, but Copy-N-Paste will do that sometimes

[cpp]

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// Problem 101: "The Blocks Problem"
// Submission by Frank "Olorin" Rizzi
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Pile
{
vector<int> ns;

void Display(int x)
{
cout<<x<<':';
if(!ns.empty())
{
cout<<' ';
int L = ns.size();
for(int i=0; i<(L-1); i++)
cout<<ns<<' ';
cout<<ns[L-1];
}
cout<<endl;
}//End Display
};//End Pile

class BlockWorld
{
public:
void Solve(int inN, vector<string> in)
{
SetUp(inN, in);
Finish();
Display();
}
//End Solve

private:
int N;
vector<string> cmds;
int CS;
int lookup[25];
Pile piles[25];

void Display()
{
for(int i=0; i<N; i++)
piles.Display(i);
}
//End Display

void Finish()
{
for(int i=0; i<CS; i++)
{
istringstream is(cmds);
string s1;
is>>s1;
if(s1=="quit") break;
int n1;
string s2;
int n2;
is>>n1>>s2>>n2;
Exe(s1, n1, s2, n2);
}//FOR
}
//End Finish

void Exe(string s1, int n1, string s2, int n2)
{
if(n1==n2) return;
if(lookup[n1]==lookup[n2]) return;
if(s1=="move" && s2=="onto")
{
Reset(n1);
Reset(n2);
Place(n1, n2);
}
else if(s1=="move" && s2=="over")
{
Reset(n1);
Place(n1, n2);
}
else if(s1=="pile" && s2=="onto")
{
Reset(n1);
PlacePile(n1, n2);
}
else if(s1=="pile" && s2=="over")
{
PlacePile(n1, n2);
}
}
//End Exe

void PlacePile(int a, int b)
{
int i;
int pa = lookup[a];
int pb = lookup;
vector<int> moving;
vector<int>::iterator it = find(piles[pa].ns.begin(), piles[pa].ns.end(), a);
int L = it-piles[pa].ns.begin();
for(i=piles[pa].ns.size()-1; i>=L; i--)
{
moving.push_back(piles[pa].ns);
piles[pa].ns.erase(piles[pa].ns.end()-1);
}//FOR
int L2 = moving.size();
for(i=L2-1; i>=0; i--)
{
piles[pb].ns.push_back(moving);
lookup[moving]=pb;
}//FOR
}
//End PlacePile

void Place(int a, int b)
{
int pa = lookup[a];
int pb = lookup;
piles[pa].ns.erase(piles[pa].ns.end()-1);
piles[pb].ns.push_back(a);
lookup[a]=pb;
}
//End Place

void Reset(int x)
{
int pindex = lookup[x];
vector<int>::iterator it = find(piles[pindex].ns.begin(), piles[pindex].ns.end(), x);
int index = it-piles[pindex].ns.begin();
int L = piles[pindex].ns.size();
for(int i=L-1; i>index; i--)
{
int k = piles[pindex].ns;
piles[pindex].ns.erase(piles[pindex].ns.begin()+i);
piles[k].ns.push_back(k);
lookup[k]=k;
}//FOR
}
//End Reset

void SetUp(int inN, vector<string> inv)
{
N = inN;
cmds=inv;
CS = inv.size();
for(int i=0; i<N; i++)
{
lookup=i;
Pile p;
p.ns.push_back(i);
piles=p;
}//FOR
}
//End SetUp

};//End BlockWorld


//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^void main()
{
int N;
cin>>N;
vector<string> v;
char t[15];
t[14]='\0';
cin.getline(t, 15, '\n');
while(true)
{
string s;
s = t;
if(s=="quit") break;

v.push_back(s);
cin.getline(t, 15, '\n');
}//WEND

BlockWorld bw;
bw.Solve(N, v);
}
//End main
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[/cpp]
[/cpp]

[ec3_limz]

I don't know what the #%!* is the problem with my source code.

Can anyone help me (either by pointing out the mistake or providing tons of test data)? Thanks.

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

int blocks, loc[25], pos[25][25], next[25];

void add(int block, int to) {
loc[block] = to * 100 + next[to];
pos[to][next[to]] = block;
next[to]++;
}

void restore(int start, int end) {
int i;

for (i = start % 100; i < end % 100; i++) {
loc[pos[start / 100]] = pos[start / 100] * 100 + next[pos[start / 100]];
pos[pos[start / 100]][next[pos[start / 100]]] = pos[start / 100];
next[pos[start / 100]]++;
pos[start / 100] = -1;
}
next[start / 100] = start % 100;
}

int main() {
char cmd[5], prep[5];
int block1, block2, temp;
int i, j;

scanf("%d", &blocks);
for (i = 0; i < blocks; i++) {
loc = i * 100;
next = 1;
pos[i][0] = i;
for (j = 1; j < blocks; j++)
pos[i][j] = -1;
}

while (true) {
scanf("%s", &cmd);
if (strcmp(cmd, "quit") == 0)
break;

scanf("%d%s%d", &block1, &prep, &block2);
if (block1 < 0 || block1 >= blocks || block2 < 0 || block2 >= blocks || loc[block1] / 100 == loc[block2] / 100)
continue;

if (strcmp(cmd, "move") == 0) {
if (strcmp(prep, "onto") == 0) {
restore(loc[block1], (loc[block1] / 100) * 100 + next[loc[block1] / 100]);
restore(loc[block2] + 1, (loc[block2] / 100) * 100 + next[loc[block2] / 100]);
add(block1, loc[block2] / 100);
}
else if (strcmp(prep, "over") == 0) {
restore(loc[block1], (loc[block1] / 100) * 100 + next[loc[block1] / 100]);
add(block1, loc[block2] / 100);
}
}
else if (strcmp(cmd, "pile") == 0) {
if (strcmp(prep, "onto") == 0) {
temp = loc[block1];
restore(loc[block2] + 1, (loc[block2] / 100) * 100 + next[loc[block2] / 100]);
for (i = loc[block1]; i % 100 < next[i / 100]; i++)
add(pos[i / 100][i % 100], loc[block2] / 100);
for (i = temp; i % 100 < next[i / 100]; i++)
pos[i / 100][i % 100] = -1;
next[temp / 100] = temp % 100;
}
else if (strcmp(prep, "over") == 0) {
temp = loc[block1];
for (i = loc[block1]; i % 100 < next[i / 100]; i++)
add(pos[i / 100][i % 100], loc[block2] / 100);
for (i = temp; i % 100 < next[i / 100]; i++)
pos[i / 100][i % 100] = -1;
next[temp / 100] = temp % 100;
}
}
}

for (i = 0; i < blocks; i++) {
printf("%d:", i);
for (j = 0; j < next[i]; j++)
printf(" %d", pos[i][j]);
printf("\n");
}

return 0;
}[/cpp]

[wrygiel]

I think the worst thing about the online judge is that there are no public tests and nobody knows what exactly what's wrong with their programs.

Can anybody send me the executable of 101 so I could generate some tests that are wrong with my program? Please!

I think this would be a good idea if there was a place from wich we could download executables of others. Maybe it is a cheat of somekind but I really don't know what's wrong with my program and I'm kinda pissed_ov.

[Fresh]

If i know your mail address... i can send mine exec

-novice