10562 - Undraw the Trees

[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.

[titid_gede]

try this input :

Code: Select all

1
#

output should be :

Code: Select all

()

hope it helps

[sharklu2000]

I have taken this case into considation. Is there some other trick input?
But thank you all the same.

[titid_gede]

what about this input :

Code: Select all

1
$
|
-
%
|
-
^
|
-
&
|
---
! (
#

output :

Code: Select all

($(%(^(&(!()(())))))

dont forget label for any code can be any printable character.. except ' ', '|' , '#' and '-'.
beside this, i have no idea..
hope it helps,

titid

[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.

Code: Select all

cutted

[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

Code: Select all

A
|
--
BC
#

should get

Code: Select all

(A(B()C()))

instead of yours:

Code: Select all

(A(B()))

[sharklu2000]

Hi hewei, thank you very much for your input and I get ac now.

[hewei]

Not at all,

[Subeen]

I am getting WA. please check my code:

Code: Select all

code removed

[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:

Code: Select all

A
|
-
A
|
-
B
#

output:

Code: Select all

(A(A(B())))

instead of yours:

Code: Select all

(A(B()))

[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]

[Subeen]

thanks, hewei. I will be more careful about making stupid assumptions.

[hewei]

Hello, windows2k!
The bug in your code is really difficult to trace,:)
See the sample:
input:

Code: Select all

2
 A
 |
---
B C
#
 A
 |
---
B
#

output:

Code: Select all

(A(B()C()))
(A(B()))

instead of yours:

Code: Select all

(A(B()C()))
(A(B()C()))

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!

[windows2k]

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.

[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;
}