![:evil:](./images/smilies/icon_evil.gif)
10562 - Undraw the Trees
Moderator: Board moderators
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
10562 - Undraw the Trees
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.
![:evil:](./images/smilies/icon_evil.gif)
Aspire to AC.
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
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
Code: Select all
1
$
|
-
%
|
-
^
|
-
&
|
---
! (
#
Code: Select all
($(%(^(&(!()(())))))
beside this, i have no idea..
hope it helps,
titid
Kalo mau kaya, buat apa sekolah?
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
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.
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.
Code: Select all
cutted
Last edited by sharklu2000 on Thu Oct 09, 2003 4:13 am, edited 1 time in total.
Aspire to AC.
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:
The input
Code: Select all
A
|
--
BC
#
Code: Select all
(A(B()C()))
Code: Select all
(A(B()))
-
- New poster
- Posts: 17
- Joined: Fri Aug 01, 2003 4:55 pm
- Location: Beijing, China
I am getting WA. please check my code:
Code: Select all
code removed
Last edited by Subeen on Sun Oct 19, 2003 9:43 pm, edited 2 times in total.
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:
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:
Code: Select all
A
|
-
A
|
-
B
#
Code: Select all
(A(A(B())))
Code: Select all
(A(B()))
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![:)](./images/smilies/icon_smile.gif)
[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]
I tried to solve the problem , and passed the input above,but still got WA
Could you point the error of my code ? thx
![:)](./images/smilies/icon_smile.gif)
[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]
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!
The bug in your code is really difficult to trace,:)
See the sample:
input:
Code: Select all
2
A
|
---
B C
#
A
|
---
B
#
Code: Select all
(A(B()C()))
(A(B()))
Code: Select all
(A(B()C()))
(A(B()C()))
10562 Undraw the Trees
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;
}