Page 19 of 43

Posted: Sat Apr 17, 2004 4:02 pm
by playerX
nevertheless, you should check your in / out routines, I guess a problem like 101 isn't the kind of problem to get time limit exceeded on..

Posted: Sun Apr 18, 2004 3:51 am
by cthompson
Thanks,

I have been working on it for two days trying to figure out where the speed issue is. I had some recurssive functions, but dropt them, and still the speed is an issue.

I can't see where else it could be. I haven't really done alot of C++ since university (mostly VB) so I thought this would be a good learning experience....this is proving to be true.

Not read ur code

Posted: Sat Jul 03, 2004 2:15 pm
by adnan2nd
I don't have time. This problem is a stack operation.Just push and pop.Giving my code . Compare.Sorry wait.

Posted: Sun Jul 04, 2004 8:48 am
by adnan2nd
This is simple stack operation,pop push. Try mine,.


#include<stdio.h>
#include<string.h>
int n;
struct stack
{
int top;
int boxes[24];
} s[25];
void init()
{
int i;
for(i=0;i<n;i++)
{
s.top=0;
s.boxes[0]=i;
}
s[24].top=-1;
}
void push(int i,int x)
{
s.top++;
s.boxes[s.top]=x;
}
int pop(int i)
{
s.top--;
return s.boxes[s.top+1];
}
//*******************************

void show()
{
int i,j;
for(i=0;i<n;i++)
{
printf("%d:",i);
for(j=0;j<=s.top;j++)
{
printf(" %d",s.boxes[j]);
}printf("\n");
}
}
int search(int x)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<=s[i].top;j++)
{
if(x==s[i].boxes[j]) return i;
}
}

}
void move_a_onto_b(int a,int b)
{
int s1,s2;
int x;
if(a==b) return;
s1=search(a);
s2=search(b);
while((x=pop(s1))!=a)
{
push(x,x);
}
while((x=pop(s2))!=b)
{
push(x,x);
}
push(s2,b);
push(s2,a);
}

void move_a_over_b(int a,int b)
{
int s1,s2;
int x;
if(a==b) return;
s1=search(a);
s2=search(b);
while((x=pop(s1))!=a)
{
push(x,x);
}
push(s2,a);
}
void pile_a_onto_b(int a,int b)
{
int s1,s2;
int x;
if(a==b) return;
s1=search(a);
s2=search(b);
while((x=pop(s1))!=a)
{
push(25,x);
}
while((x=pop(s2))!=b)
{
push(x,x);
}
push(s2,b);
push(s2,a);
while(s[24].top!=-1)
{
push(s2,pop(25));
}
}

void pile_a_over_b(int a,int b)
{
int s1,s2;
int x;
if(a==b) return;
s1=search(a);
s2=search(b);
while((x=pop(s1))!=a)
{
push(24,x);
}
push(s2,a);
while(s[25].top!=-1)
{
push(s2,pop(24));
}
}




main()
{
char c1[5],c2[5],c3[5],c4[5];
int i,a,b;
scanf("%d",&n);
init();
while(1)
{
scanf("%s",c1);
if(!strcmp(c1,"quit")) {show();break;}
if(!strcmp(c1,"move"))
{
scanf("%d %s",&a,c2);
if(!strcmp(c2,"onto")) {scanf("%d",&b);move_a_onto_b(a,b);}
else if(!strcmp(c2,"over")) {scanf("%d",&b);move_a_over_b(a,b);}
}
else if(!strcmp(c1,"pile"))
{
scanf("%d %s",&a,c2);
if(!strcmp(c2,"onto")) {scanf("%d",&b);pile_a_onto_b(a,b);}
else if(!strcmp(c2,"over")) {scanf("%d",&b);pile_a_over_b(a,b);}
}

}

return 0;
}

I always got WA for 101,I don't know why

Posted: Mon Jul 05, 2004 6:21 pm
by fishbao
I have tried many times,but it always tells me WA.Could you give me some complex test data?
[cpp]
#include <iostream>
#include <string.h>
using namespace std;
class Blocks
{
private:
int block[25][25];
int top[25];
int n;
public:
Blocks(int N);
void mot(int x1,int x2,int y1,int y2);//move onto
void moe(int x1,int x2,int y1,int y2);//move over
void pot(int x1,int x2,int y1,int y2);//pile onto
void poe(int x1,int x2,int y1,int y2);//pile over
int search(int a,int b,int &x1,int &x2,int &y1,int &y2);
void readcommand();
void print();
};
Blocks::Blocks(int N)
{
int i;
n=N;

for (i=0;i<n;i++)
{
block[0]=i;
top=1;
}
}
int Blocks::search(int a,int b,int &x1,int &x2,int &y1,int &y2)
{
int x,y;
for (x=0;x<n;x++)
for(y=0;y<top[x];y++)
{
if(a==block[x][y])
{
y1=y;
x1=x;
if(b==block[x][y])
return 0;
}
if(b==block[x][y])
{
y2=y;
x2=x;
if(a==block[x][y])
return 0;
}
}
return 1;
}
void Blocks::readcommand()
{
char *command1,*command2;
int x,y,x1,y1,x2,y2;
command1=new char[4];
command2=new char[4];
while(cin>>command1&&strcmp(command1,"quit"))
{
cin>>x>>command2>>y;
if(!strcmp(command1,"move")&&!strcmp(command2,"onto"))
{
if(search(x,y,x1,x2,y1,y2))
mot(x1,x2,y1,y2);
}else
if(!strcmp(command1,"move")&&!strcmp(command2,"over"))
{
if(search(x,y,x1,x2,y1,y2))
moe(x1,x2,y1,y2);
}
else
if(!strcmp(command1,"pile")&&!strcmp(command2,"onto"))
{
if(search(x,y,x1,x2,y1,y2))
pot(x1,x2,y1,y2);
}
else
if(!strcmp(command1,"pile")&&!strcmp(command2,"over"))
{
if(search(x,y,x1,x2,y1,y2))
poe(x1,x2,y1,y2);
}
}
}
void Blocks::mot(int x1,int x2,int y1,int y2)
{
int i;
if(y1!=top[x1]-1)
{

for (i=top[x1]-1;i>y1;i--)
{
block[block[x1]][0]=block[x1];
top[x1]--;
top[block[x1]]++;
}

}
if(y2!=top[x2]-1)
{
for (i=top[x2]-1;i>y2;i--)
{
block[block[x2]][0]=block[x2];
top[x2]--;
top[block[x2]]++;
}
}
block[x2][y2+1]=block[x1][y1];
top[x2]++;
top[x1]--;
}
void Blocks::moe(int x1,int x2,int y1,int y2)
{
int i;
if(y1!=top[x1]-1)
{

for (i=top[x1]-1;i>y1;i--)
{
block[block[x1]][0]=block[x1];
top[x1]--;
top[block[x1][i]]++;
}

}
block[x2][top[x2]]=block[x1][y1];
top[x2]++;
top[x1]--;
}
void Blocks::pot(int x1,int x2,int y1,int y2)
{
int i,tops,k;
if(y2!=top[x2]-1)
{
for (i=top[x2]-1;i>y2;i--)
{
block[block[x2][i]][0]=block[x2][i];
top[x2]--;
top[block[x2][i]]++;
}
}
tops=top[x1];
for(i=y1,k=1;i<tops;i++,k++)
{
block[x2][y2+k]=block[x1][i];
top[x1]--;
top[x2]++;
}
}
void Blocks::poe(int x1,int x2,int y1,int y2)
{
int i,j,k,l;
i=top[x1];
j=top[x2];
for(k=y1,l=0;k<i;k++,l++)
{
block[x2][j+l]=block[x1][k];
top[x2]++;
top[x1]--;
}

}

void Blocks::print()
{
int i,j;
for(j=0;j<n;j++)
{
cout<<j<<": ";
if(top[j])
for (i=0;i<top[j];i++)
cout<<block[j][i]<<" ";
cout<<endl;
}
}
int main()
{

int n;
cin>>n;
Blocks block(n);
block.readcommand();
block.print();
return 1;
}





[/cpp]

101-WA Help me!!!

Posted: Wed Jul 14, 2004 4:39 pm
by Karthekeyan
Here's my code!!!Some one pls help me!!!
[cpp]
#include<iostream>
#include<string>
using namespace std;
main()
{
char cmd[5],cmd2[5],acmd2[5],acmd[5];
int n,b,a,i,j,l,f[25],h[25][25],temp,temp1,tempa1,tempa2,tempb1,tempb2;
for(i=0;i<25;i++)
{
f=-1;
for(j=0;j<25;j++)
{
h[j]=-1;
}
}
cin>>n;
for(i=0;i<n;i++)
{
f=i;
}
for(i=0;i<n;i++)
{
h[0]=i;
}
while(cin>>cmd)
{
//////////move///////////
if(strcmp(cmd,"move")==0)
{
cin>>a>>acmd>>b;
if(strcmp(acmd,"onto")==0)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==a)
{
tempa1=i;
tempa2=j;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==b)
{
tempb1=i;
tempb2=j;
}
}
}
//cout<<"\ntempa1="<<tempa1<<"\ttempa2="<<tempa2<<"\ttempb1="<<tempb1<<"\ttempb2="<<tempb2<<'\n';
if(tempa1!=tempb1)
{
for(j=tempa2;j<n;j++)
{
if(h[tempa1][j]!=-1)
{
temp=h[tempa1][j];
h[temp][0]=temp;
h[tempa1][j]=-1;
}
}
for(j=(tempb2+1);j<n;j++)
{
if(h[tempb1][j]!=-1)
{
temp=h[j];
h[temp][0]=temp;
h[j]=-1;
}
}
h[tempb1][tempb2+1]=a;
h[a][0]=-1;
}
}

else if(strcmp(acmd,"over")==0)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==a)
{
tempa1=i;
tempa2=j;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==b)
{
tempb1=i;
tempb2=j;
}
}
}
//cout<<"\ntempa1="<<tempa1<<"\ttempa2="<<tempa2<<"\ttempb1="<<tempb1<<"\ttempb2="<<tempb2<<'\n';
if(tempa1!=tempb1)
{
for(j=tempa2;j<n;j++)
{
if(h[tempa1][j]!=-1)
{
temp=h[tempa1][j];
h[temp][0]=temp;
h[tempa1][j]=-1;
}
}
for(j=0;j<n;j++)
{
if(h[tempb1][j]==-1)
{
temp=j;
//cout<<"\ntemp="<<temp<<'\n';
break;
}
}
h[a][0]=-1;
h[tempb1][temp]=a;
}
}
}
//////////pile//////////
else if(strcmp(cmd,"pile")==0)
{
cin>>a>>acmd>>b;
if(strcmp(acmd,"onto")==0)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==a)
{
tempa1=i;
tempa2=j;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[j]==b)
{
tempb1=i;
tempb2=j;
}
}
}
//cout<<"\ntempa1="<<tempa1<<"\ttempa2="<<tempa2<<"\ttempb1="<<tempb1<<"\ttempb2="<<tempb2<<'\n';
if(tempa1!=tempb1)
{
for(j=tempb2+1;j<n;j++)
{
if(h[tempb1][j]!=-1)
{
temp=h[tempb1][j];
h[temp][0]=temp;
h[tempb1][j]=-1;
}
}
for(j=tempa2,l=tempb2;j<n,l<n;j++,l++)
{
if(h[tempa1][j]!=-1)
{
h[tempb1][l+1]=h[tempa1][j];
h[tempa1][j]=-1;
}
}
}
}

else if(strcmp(acmd,"over")==0)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[i][j]==a)
{
tempa1=i;
tempa2=j;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(h[i][j]==b)
{
tempb1=i;
tempb2=j;
}
}
}
//cout<<"\ntempa1="<<tempa1<<"\ttempa2="<<tempa2<<"\ttempb1="<<tempb1<<"\ttempb2="<<tempb2<<'\n';
if(tempa1!=tempb1)
{
for(j=tempb2;j<n;j++)
{
if(h[tempb1][j]==-1)
{
temp=j;
break;
}
}
//cout<<"\ntemp="<<temp<<'\n';
for(j=tempa2,l=temp;j<n,l<n;j++,l++)
{
if((h[tempa1][j]!=-1)&&(h[tempb1][l]==-1))
{
h[tempb1][l]=h[tempa1][j];
h[tempa1][j]=-1;
}
}
h[tempb1][tempb2]=b;
}
}
}
///////////////////////////////////////////////////////
else if(strcmp(cmd,"quit")==0)
break;
//////////////output///////////////////////////////////
/*for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout<<h[i][j]<<'\t';
}
cout<<'\n';
}*/
}
for(i=0;i<n;i++)
{
cout<<i<<":";
for(j=0;j<n;j++)
{
if(h[i][j]!=-1)
{
cout<<" "<<h[i][j];
}

}
cout<<'\n';
}
return(0);
}

[/cpp]

Some one pls help me out!!!! :o [/cpp]

Why 101 Time Limit Exceed ?

Posted: Tue Jul 20, 2004 5:33 am
by frankhuhu
:cry: [cpp]
here is my code. I have tried for a long time. But why TLE?
Is there anyone who can give me a more simple method?

#include <iostream.h>
#include <string.h>

int main()
{
char cmd1[5],cmd2[5];
int block[25][25];
int n,a,b,x,y,i,j;
int ta1,ta2,tb1,tb2;//a and b position
//initilize block and f;
for (i=0;i<25;i++)
for (j=0;j<25;j++)
block[j]=-1;
cin>>n;
for (j=0;j<n;j++)
block[j][0]=j;

while (cin>>cmd1)
{
if (strcmp("quit",cmd1)==0) break;
cin>>a>>cmd2>>b;
if (strcmp("move",cmd1)==0)
{
////move a onto b
if (strcmp("onto",cmd2)==0)
{
//find a&b's position
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}
//return any blocks that are stacked on top of blocks a and b to their initial positions.
if (block[ta1][ta2+1]>=0)
{
int tmp=ta2+1;
while (block[ta1][tmp]>=0)
{
int temp=block[ta1][tmp];
block[ta1][tmp]=-1;
block[temp][0]=temp;
tmp++;
}
}

if (block[tb1][tb2+1]>=0)
{
int tmp=tb2+1;
while (block[tb1][tmp]>=0)
{
int temp=block[tb1][tmp];
block[tb1][tmp]=-1;
block[temp][0]=temp;
tmp++;
}
}
//find a&b's position again!
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}
//begin move a onto b
block[tb1][tb2+1]=a;
block[ta1][ta2]=-1;
//end move a onto b
}


////move a over b
if (strcmp("over",cmd2)==0)
{
//find a&b's position
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}
//return any blocks that are stacked on top of blocks a to their initial positions.
if (block[ta1][ta2+1]>=0)
{
int tmp=ta2+1;
while (block[ta1][tmp]>=0)
{
int temp=block[ta1][tmp];
block[ta1][tmp]=-1;
block[temp][0]=temp;
tmp++;
}
}
//find a&b's position again!
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}

//find the position that can be put by a;
int tmp1;
if (block[tb1][tb2+1]>=0)
{
tmp1=tb2+1;
while (block[tb1][tmp1]>=0)
{
tmp1++;
}
}
//begin move a over b;
if (ta1!=tb1)
{
block[tb1][tmp1]=a;
block[ta1][ta2]=-1;
}
//end move a over b;
}
}

if (strcmp("pile",cmd1)==0)
{
////pile a onto b
if (strcmp("onto",cmd2)==0)
{
//find a&b's position
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}

//return any blocks that are stacked on top of blocks b to their initial positions.
if (block[tb1][tb2+1]>=0)
{
int tmp=tb2+1;
while (block[tb1][tmp]>=0)
{
int temp=block[tb1][tmp];
block[tb1][tmp]=-1;
block[temp][0]=temp;
tmp++;
}
}
//find a&b's position again
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}
//find the blocks that are above a;
int tmp1;
if (block[tb1][tb2+1]>=0)
{
tmp1=tb2+1;
while (block[tb1][tmp1]>=0)
{
tmp1++;
}
}
//begin pile a onto b;
int cnt=tmp1-ta2+1;
int tmp2=tb2+1;
int tmp3=ta2;
for (i=0;i<cnt;i++)
{
int temp=block[ta1][tmp3];
block[ta1][tmp3]=-1;
block[tb1][tmp2]=temp;
tmp2++;tmp3++;
}
//end pile a onto b;


}

////pile a over b
if (strcmp("over",cmd2)==0)
{
int tmp1=1,tmp2=1;
//find a&b's position
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==a) {ta1=x;ta2=y;break;}
}
for (x=0;x<n;x++)
for (y=0;y<n;y++)
{
if (block[x][y]==b) {tb1=x;tb2=y;break;}
}
if (ta1!=tb1)
{
//find the blocks that are above a;
if (block[ta1][ta2+1]>=0)
{
tmp1=ta2+1;
while (block[ta1][tmp1]>=0)
{
tmp1++;
}
}

//find the blocks that are above b;
if (block[tb1][tb2+1]>=0)
{
tmp2=tb2+1;
while (block[tb1][tmp1]>=0)
{
tmp2++;
}
}
//begin pile a over b;
int cnt=tmp1-ta2;
int tmp3=ta2;
int tmp4=tmp2;
for (j=0;j<cnt;j++)
{
int temp=block[ta1][tmp3];
block[ta1][tmp3]=-1;
block[tb1][tmp4]=temp;
tmp4++;tmp3++;
}

//end pile a over b;


}

}

}

}

//print result;
for(i=0;i<n;i++)
{
cout<<i<<":";
for(j=0;j<n;j++)
{
if(block[j]!=-1)
{
cout<<" "<<block[j];
}

}
cout<<'\n';
}
return 0;
}[/quote][/cpp]

Posted: Tue Jul 20, 2004 12:17 pm
by chunyi81
I see you did not handle invalid input in your program. Test your program at least with the sample input or with the inputs in this forum before submitting to the OJ. The inputs help a lot.

Also, from the problem description:
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.

101 in C Accepted (P.E.) help

Posted: Tue Jul 20, 2004 3:16 pm
by Ghust_omega
i got Accepted (P.E.) but i dont know how to fix the presentetion of the numbers , i put HERE where i print the numbers the funtion is below,please tell me what i have to change in my code for i have accept thanks
CUT

why so lengthy

Posted: Tue Jul 20, 2004 3:56 pm
by sohel
Ghust_omega:

I just changed two parts of your code and managed to avoid P.E.

A part of your code
[c]
void showStack(Pila *pila){
pNodo n = *pila;
int inv[26];
int p;
p = 0;
while(1){
if(n == NULL){
printf(" ");
break;
}
inv[p] = (int)n -> valor;
p++;
if(n -> sig == NULL)
break;
n = n -> sig;

}
p--;
while(p>=0){
printf("%i ",inv[p]);
p--;
}
printf("\n");

}
[/c]

changed code
[c]
void showStack(Pila *pila){
pNodo n = *pila;
int inv[26];
int p;
p = 0;
while(1){
if(n == NULL){
// printf(" ");
break;
}
inv[p] = (int)n -> valor;
p++;
if(n -> sig == NULL)
break;
n = n -> sig;

}
p--;
while(p>=0){
printf(" %i",inv[p]);
p--;
}
printf("\n");

}
[/c]

Note that printf(" ") is omitted and
printf("%i ") is replaced by printf(" %i");

Hope it helps.

And remove your code as it's AC. :wink:

Posted: Tue Jul 20, 2004 4:01 pm
by Ghust_omega
Thanks a lot i know someone help me

Posted: Tue Jul 20, 2004 4:01 pm
by Ghust_omega
Thanks a lot sohel i know someone help me

Posted: Tue Jul 20, 2004 4:02 pm
by Ghust_omega
Thanks a lot sohel i know someone help me you are right!!!! i got AC jeje

Compiler Error? (but works on my machine)

Posted: Tue Jul 27, 2004 9:39 am
by Minilek
I'm not sure exactly why I'm getting a compiler error. The judge
seems to have a problem with my declaration of command and prep,
but the program compiles and works fine on my computer (I'm
also using gcc). I've also tried submit-o-matic just in case my email
client was adding in extra weird characters, but still a compile error.

The source is as below:

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct mystack mystack;
struct mystack {
int top,stck[30];
};

mystack stacks[30];
int locs[30];

int peek(int loc) {
return stacks[loc].stck[stacks[loc].top-1];
}

void push(int loc, int a) {
locs[a] = loc;
stacks[loc].stck[stacks[loc].top++] = a;
}

int size(int loc) {
return stacks[loc].top;
}

void putback(int loc) {
locs[peek(loc)] = peek(loc);
push(peek(loc),peek(loc));
stacks[loc].top--;
}

int pop(int loc) {
return stacks[loc].stck[--stacks[loc].top];
}

main() {
int i,j,k,x,y,z,n;
scanf("%d",&n);
char command[20],prep[20];
for (i=0;i<30;i++) stacks.top = 0;
for (i=0;i<n;i++) push(i,i);
while (1) {
scanf("%s",command);
if (!strcmp(command,"quit")) break;
scanf("%d %s %d",&x,prep,&y);
if (locs[x]==locs[y]) continue;
if (!strcmp(prep,"onto")) while (peek(locs[y])!=y) putback(locs[y]);
if (!strcmp(command,"move")) while (peek(locs[x])!=x) putback(locs[x]);
int ind=0,buff[30];
while (peek(locs[x])!=x) buff[ind++] = pop(locs[x]);
buff[ind++] = pop(locs[x]);
for (i=ind-1;i>=0;i--) push(locs[y],buff);
}
for (i=0;i<n;i++) {
printf("%d:",i);
for (j=0;j<size(i);j++) printf(" %d",stacks.stck[j]);
printf("\n");
}
exit(0);
}
[/c]

Thanks.

Problem #

Posted: Tue Jul 27, 2004 9:57 am
by Minilek
Forgot to mention, this is problem # 101.