10562 - Undraw the Trees

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

10562 - Undraw the Trees

Post by sharklu2000 » Wed Oct 08, 2003 6:34 am

My program passed all my input and I really don't know why it always get wa. :evil: Can anybody give me some critical input? Many thanks.
Aspire to AC.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Oct 08, 2003 7:18 am

try this input :

Code: Select all

1
#
output should be :

Code: Select all

()
hope it helps :)
Kalo mau kaya, buat apa sekolah?

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Wed Oct 08, 2003 8:51 am

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Oct 08, 2003 9:09 am

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
Kalo mau kaya, buat apa sekolah?

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Wed Oct 08, 2003 9:35 am

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
Last edited by sharklu2000 on Thu Oct 09, 2003 4:13 am, edited 1 time in total.
Aspire to AC.

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China

Post by hewei » Wed Oct 08, 2003 5:06 pm

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
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » Thu Oct 09, 2003 4:17 am

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

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China

Post by hewei » Thu Oct 09, 2003 6:12 am

Not at all, :)

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Thu Oct 09, 2003 10:16 am

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.

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China

Post by hewei » Thu Oct 09, 2003 4:49 pm

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sat Oct 11, 2003 5:14 am

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Oct 11, 2003 12:28 pm

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

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China

Post by hewei » Sat Oct 11, 2003 4:43 pm

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sun Oct 12, 2003 11:22 am

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.

jiewlmrh
New poster
Posts: 1
Joined: Thu Aug 30, 2012 5:04 pm

10562 Undraw the Trees

Post by jiewlmrh » Thu Aug 30, 2012 5:09 pm

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

Post Reply

Return to “Volume 105 (10500-10599)”