Page 1 of 2
10562 - Undraw the Trees
Posted: Wed Oct 08, 2003 6:34 am
by sharklu2000
My program passed all my input and I really don't know why it always get wa.
Can anybody give me some critical input? Many thanks.
Posted: Wed Oct 08, 2003 7:18 am
by titid_gede
try this input :
output should be :
hope it helps
Posted: Wed Oct 08, 2003 8:51 am
by sharklu2000
I have taken this case into considation. Is there some other trick input?
But thank you all the same.
Posted: Wed Oct 08, 2003 9:09 am
by titid_gede
what about this input :
output :
dont forget label for any code can be any printable character.. except ' ', '|' , '#' and '-'.
beside this, i have no idea..
hope it helps,
titid
Posted: Wed Oct 08, 2003 9:35 am
by sharklu2000
Thank you for your kindness but my program can also handle this input.
I almost give up. My code is as follows. I simply deal with each line and construct the tree which is a left child right sibling tree. After that I run the forward dfs. Anyone finding out the fault is appreciated.
Posted: Wed Oct 08, 2003 5:06 pm
by hewei
Hi, sharklu2000. I noticed that you assume that the children of a same parent node will be at least a 'space' apart. But since this is not specially mentioned in the desciption, I think there could be such situations where the children are sticked together. For example:
The input
should get
instead of yours:
Posted: Thu Oct 09, 2003 4:17 am
by sharklu2000
Hi hewei, thank you very much for your input and I get ac now.
Posted: Thu Oct 09, 2003 6:12 am
by hewei
Not at all,
Posted: Thu Oct 09, 2003 10:16 am
by Subeen
I am getting WA. please check my code:
Posted: Thu Oct 09, 2003 4:49 pm
by hewei
Hello, Subeen!
You have carelessly assumed:
1. All the labels of the tree is different since it was that in the sample.
2. Total number of nodes in a tree will not exceed 210 as you have declared the array "abc" to contain only 210 elements.
Theoretically, both of the two points above will stop you from getting AC. But it seems that the second one didn't take effect, otherwise, you would have got RE.
Please see the sample below:
input:
output:
instead of yours:
Posted: Sat Oct 11, 2003 5:14 am
by windows2k
hello, hewei
I tried to solve the problem , and passed the input above,but still got WA
Could you point the error of my code ? thx
[cpp]
#include <stdio.h>
#include <string.h>
char s[210][210],str[210];
int depth;
bool valid(char c)
{
if(c==' '||c=='\0'||c=='\n'||c=='-'||c=='|'||c=='#') return false;
return true;
}
void print(int r,int c,char ch)
{
putchar(ch);
putchar('(');
int left,right;
if(r+3<=depth&&s[r+1][c]=='|')
{
for(left=c;left>=0&&s[r+2][left]=='-';left--) ;
for(right=c;s[r+2][right]=='-';right++) ;
for(int k=left+1;k<right;k++)
if(valid(s[r+3][k])) print(r+3,k,s[r+3][k]);
}
putchar(')');
}
int main()
{
int N;
gets(str);
sscanf(str,"%d",&N);
while(N--)
{
for(depth=0;;depth++)
{
gets(s[depth]);
int k;
for(k=strlen(s[depth]);k>=0;k--)
if(s[depth][k]!='\0'&&s[depth][k]!=' ') break;
s[depth][k+1]='\0';
if(strcmp(s[depth],"#")==0) break;
}
printf("(");
for(int i=0;i<strlen(s[0]);i++)
if(valid(s[0]
)) {
print(0,i,s[0]);
break;
}
printf(")\n");
}
return 0;
}
[/cpp]
Posted: Sat Oct 11, 2003 12:28 pm
by Subeen
thanks, hewei. I will be more careful about making stupid assumptions.
Posted: Sat Oct 11, 2003 4:43 pm
by hewei
Hello, windows2k!
The bug in your code is really difficult to trace,:)
See the sample:
input:
output:
instead of yours:
Till now, you will have got to know what is all happening to your program. You forgot to flush the array 's' for every fresh 'while' loop!
Posted: Sun Oct 12, 2003 11:22 am
by windows2k
hewei wrote:Hello, windows2k!
The bug in your code is really difficult to trace,:)
Till now, you will have got to know what is all happening to your program. You forgot to flush the array 's' for every fresh 'while' loop!
Thanks hewei
I finally get AC.
10562 Undraw the Trees
Posted: Thu Aug 30, 2012 5:09 pm
by jiewlmrh
I don't know why my code is always WA!!!
Code: Select all
#include<iostream>
#include<fstream>
using namespace std;
char data[5000][250],result[100001];
int resultTop,recordLine;
void buildTree(int line,int location)
{
if(line>recordLine) recordLine=line;
if(data[++line][location]=='|')
{
int tmp1=location,tmp2=location;
line++;
while(data[line][tmp1--]=='-');
while(data[line][tmp2++]=='-');
tmp1+=2;tmp2-=2;
line++;
result[resultTop++]='(';
for(int i=tmp1;i<=tmp2;i++)
{
if(data[line][i]!=' ')
{
result[resultTop++]=data[line][i];
buildTree(line,i);
}
}
result[resultTop++]=')';
}else{
result[resultTop++]='(';
result[resultTop++]=')';
}
}
int main()
{
//ifstream fin("test.txt");
char ch;
int i=0,j=0,n,k;
cin>>n;
cin.get(ch);
cin.get(ch);
while(!cin.eof()){
data[j][i]=ch;
if(ch=='\n')
{
for(int t=i;t<=201;t++) data[j][t]=' ';
j++;
i=-1;
}
i++;
cin.get(ch);
}
recordLine=-2;
while(n--){
resultTop=0;
k=0;
while(data[recordLine+2][k++]==' ');
k--;
result[resultTop++]='(';
if(data[recordLine+2][k]!='#'){
result[resultTop++]=data[recordLine+2][k];
buildTree(recordLine+2,k);
}
result[resultTop++]=')';
for(int i=0;i<resultTop;i++)
cout<<result[i];
cout<<endl;
}
return 0;
}