## 112 - Tree Summing

Moderator: Board moderators

Innovative Cat
New poster
Posts: 1
Joined: Sun Jul 28, 2002 8:23 am
Location: China
Contact:

### [b]Help! Problem 112. Wrong Answer!!!!!!![/b]

[pascal]
Program P112_Tree_Summing;
Var
t : String;
Aim : Integer;
Ch : Char;
Procedure GetChar(var ch:Char);
Begin
While Not Eof(input) And
(Ch<>'(') And
(Ch<>')') And
(Ch<>'-') And
(Ch<>'+') And
((Ch>'9') Or
End;
Function Find(Sum:Integer):Byte;
Var
x,y,Num : Integer;
Begin
GetChar(Ch);
If Ch=')' Then Begin
GetChar(Ch);
Find:=2;
Exit;
End;
t:='';
While Ch<>'(' Do
Begin
t:=t+Ch;
GetChar(Ch);
End;
Val(t,Num,Num);
Inc(Sum,Num);
x:=Find(Sum);
y:=Find(Sum);
If (x=0) Or (y=0) Or
((x=2) And (y=2) And (Sum=Aim))
Then Find:=0
Else Find:=1;
GetChar(Ch);
End;
Begin
GetChar(ch);
While Not Eof(Input) Do
Begin
t:='';
While Ch<>'(' Do
Begin
t:=t+Ch;
GetChar(Ch);
End;
If Eof(Input) Then Break;
Val(t,Aim,Aim);
If Find(0)=0
Then Writeln('yes')
Else Writeln('no');
End;
End.
[/pascal][/code]

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

### 112 SIGSEGV

"Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference"

to my programme and I can't see way...

[pascal]
program p112(input,output);
type pnod=^nod;
nod=record
nr:integer;
st,dr:pnod;
end;

s:string;
p,nr:integer;

var n:integer;
begin
if s[p+1]=')' then
begin
p:=p+1;
end
else
begin
n:=0;
p:=p+1;
while s[p] in ['0'..'9'] do
begin
n:=n*10+ord(s[p])-ord('0');
p:=p+1;
end;
p:=p+1;
p:=p+1;
end;
end;

begin
if s=0 then
verif:=true
else
verif:=false
else
end;
procedure sterg(var s:string);
var i:integer;
begin
i:=pos(' ',s);
while i<>0 do
begin
delete(s,i,1);
i:=pos(' ',s);
end;
end;

procedure numara(s:string;var n1,n2:integer);
var i:integer;
begin
for i:=1 to length(s) do
if s='(' then
n1:=n1+1
else
if s=')' then
n2:=n2+1;
end;

procedure citire(var s:string; var nr:integer);
var i,cod:integer;
s1:string;
n1,n2:integer;
begin
while s[1]=' ' do
delete(s,1,1);
while s[length(s)]=' ' do
delete(s,length(s),1);
i:=pos(' ',s);
if i=0 then
begin
val(s,nr,cod);
s:='';
end
else
begin
s1:=copy(s,1,i-1);
val(s1,nr,cod);
delete(s,1,i);
sterg(s);
end;
n1:=0; n2:=0;
numara(s,n1,n2);
while (n1<>n2) or ((n1=n2) and (n1=0)) do
begin
sterg(s1);
numara(s1,n1,n2);
insert(s1,s,length(s)+1);
end;
end;

begin
begin
end;
end;

begin
while not eof(input) do
begin
citire(s,nr);
p:=1;
writeln('yes')
else
writeln('no');
end;
end.
[/pascal]

Can you help me???

Thanks

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

### Annoying Runtime Error

Sorry I didn't take a close look on your programme. But, as far as I know, dividing by 0 or trying to manipulate the pointer which is assigned NIL would usually lead to Runtime Error. Try to enlarge your array or something like that.
James.Hao (Bonjour!)

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan

### 112 -Tree Summing [runtime-error](SIGSEGV)

i don't find where run-time error....
who can tell me why..

[cpp]
#include<iostream>
#include<string>
#include<queue>
using namespace std;

queue<int> qu;
string sData="";
int start=0;
int rightx=0;
int tree_length=0;
int *position;

void input_data();
void run(string s1);
void cut(string s1);
int check(string s1);
void main(){
input_data();
}
void input_data(){
string sBuff;
while(!cin.eof()){
getline(cin,sBuff);
if(sBuff=="")continue;
cut(sBuff);
if(check(sData)==1 && sData.find('(',0)!=-1){
long value;
value = atol( sData.substr( 0,sData.find('(',0)-0).c_str() );
rightx++;
run( sData.substr( sData.find('(',0)+1 , sData.length() ) );
sData="";
start=0;
int yes=0;
position = new int[tree_length];
while(qu.size()!=0){
int k1,k2,k3;
k1=qu.front();
qu.pop();
k2=qu.front();
qu.pop();
if(k2>0)
position[k2-1]=k1;
else{
position[-1*k2-1]=k1;
long cost=0;
for(k3=0;k3<-1*k2;k3++)
cost+=position[k3];
if(value==cost){
yes=1;
break;
}
}
}
tree_length=0;
delete position;
if(yes==1) cout << "yes" << endl;
else cout << "no" << endl;
}
}
}
void run(string s1){
int k1;
for(k1=0;k1<s1.length();){
if( s1.at(k1)=='('){
rightx++;
k1++;
}
else if( s1.at(k1)==')'){
rightx--;
k1++;
}
else{
long node;
node = atol( s1.substr( k1,s1.find('(',k1)-k1).c_str() );
k1=s1.find('(',k1);
qu.push( node );
if( s1.substr( k1 , 4 )=="()()" ){
if(tree_length < rightx) tree_length = rightx;
qu.push(-1*rightx);
k1+=4;
}
else
qu.push( rightx );
}
}
}
void cut(string s1)
{
int p,q;
q=0;
p=s1.find(" ");
for(;p!=-1;){
if(p!=q)
sData+=s1.substr(q,p-q);
q=p+1;
p=s1.find(" ",p+1);
}
p=s1.length();
if(p!=q)
sData+=s1.substr(q,p-q);
}
int check(string s1){
int k1;
for(k1=start;k1<s1.length();k1++){
if(s1.at(k1)=='(') rightx++;
else if(s1.at(k1)==')')
rightx--;
}
start=s1.length();
if(rightx!=0) return 0;
else return 1;
}
[/cpp]

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

### WA 112...

I have test as many case(negative number,empty tree) as I can, but still get WA, can anybody help me?

Code: Select all

``````/* problem 112 C++ */
#include<iostream.h>
#include<vector>

char cursor,sign,precursor;
int  num,query,i,j,sum,level;
bool result;

using namespace std;

void main(void)
{
vector<int> numlv;
vector<int> number;
while(cin>>query)
{
cin>>cursor; /* read in first "(" */
level = 1;
/* read in one case of input */
while (level != 0)
{
cin>>cursor;
if ((cursor != ')')&&(cursor != '('))
{
if (cursor == '-')
{
sign = '-';
cin>>cursor;
}
else
sign = '+';
num = 0;
while ((cursor > 47)&&(cursor < 58))
{
if (num == 0)
num = cursor - 48;
else
num = num * 10 + cursor - 48;
cin>>cursor;
}
if (sign == '+')
number.push_back(num);
else
number.push_back(0-num);
numlv.push_back(level);
level++;
}
else if (cursor == ')') /* read in ")" */
{
if (precursor == '(')
{
number.push_back(0);
numlv.push_back(0);
}
level--;
}
else /* read in "(" */
level++;
precursor = cursor;
}
if (number.size() == 0) /* when null tree occurred */
cout<<"no\n";
else
{
result = false;
for (i=0;i<number.size()-2;i++)
{
sum = 0;
if ((numlv[i] != 0)&&(numlv[i+1] == 0)&&(numlv[i+2] == 0))
{
level = numlv[i];
for (j=i;j>=0;j--)
{
if (numlv[j] == level)
{
sum = sum + number[j];
if (level == 1)
break;
level--;
}
}
}
if (sum == query)
result = true;
}
if (result == true)
cout<<"yes\n";
else
cout<<"no\n";
}
number.clear();
numlv.clear();
}
}

``````

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:

### 112

[/b] How many leaf to root path is in the following tree

22 (5(10()(20))(10()()))

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I think that's incorrect input data ...
Maybe it should be

Code: Select all

``22 (5(10()(20()()))(10()()))  ``
??

Dominik

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
Is it a binary tree?
why you put those blank leaves after 20?
We are all in a circular way, no advances, only moving and moving!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If I should remember it should be binary tree ...
But I can made a mistake
Grammas,which is given to this problem, says that's binary tree ...

Dominik

luzi82
New poster
Posts: 4
Joined: Wed Oct 16, 2002 3:18 pm

### if you find 112 is difficult............

think of the negative input

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

test
Last edited by nghiank on Sun Apr 22, 2007 3:41 pm, edited 1 time in total.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
to problem 112:

input:
9 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
output:
no

I think you might have bug here.

Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm

### P 112: Why WA? :o

I've considered negetive case...empty tree....but still WA.

#include<stdio.h>
#include<string.h>

char fun1();
signed long int Sum[15000],count=-1,countf=0,flagf=0,countob=1,countcb=0,flagclose=0;
void main(void)
{
freopen("h:\\tc\\testing\\f1.in" , "r",stdin);
signed long int sum=0,s=0,s1,input,first,flag=0,flag2=0,flags=0,count2=0,count3=0,ritu=0;
char cath;
while(scanf("%ld",&first)==1)
{
flagclose=0;
while(countob>countcb&&flagclose==0)
{
ritu++;
if(ritu==1){countob=0;countcb=0;}
cath=fun1();
if(ritu==1){if(cath==' '||cath=='\n'){ritu=0;countob=1;countcb=0;}}
if(cath=='(')
{
flags=0;
if(scanf("%ld",&input)==1)
{
Sum[s++]=input;
count3=0;
}
else count3++;
}
else if(cath==')')
{
count2++;
if(count3==2&&count2==3){count-=3;count2-=3;for(s1=0;s1<s;s1++){sum+=Sum[s1];flag2=1;}}
if(sum==first)
{
sum=0;
flag=1;
}
}
sum=0;
if(flag2==1){Sum[s-1]=0;flag2=0;count3=0;flags=1;s=s-1;}
if(flags==1&&count2==1){Sum[s-1]=0;s=s-1;flags=0;count-=1;count2=0;}
if(count==count2){for(s1=1;s1<s;s1++)Sum[s1]=0;count=0;count2=0;}
if(flag!=1&&cath=='e')
{
printf("no\n");
memset(Sum,0,sizeof(Sum)-1);
count=-1;countf=0;flagf=0;countob=1;countcb=0;flag=0;flag2=0;count2=0;count3=0;
sum=0;s=0;ritu=0;
flagclose=1;
}
if(flag==1&&cath=='e')
{
printf("yes\n");
memset(Sum,0,sizeof(Sum)-1);
count=-1;countf=0;flagf=0;flag=0;flag2=0;count2=0;count3=0;
sum=0;s=0;
flagclose=1;
}
}
countob=1;countcb=0;ritu=0;
}
}

char fun1()
{
char ch;
scanf("%c",&ch);
countf++;
if(ch=='(')countob++;
if(ch==')')countcb++;
if(countf==2){if(ch=='('){count++;flagf=1;} }
else if(flagf==1)if(ch=='('){count++;}
if(countob!=0&&countcb!=0&&countob==countcb)return 'e';
else if(ch!=' '||ch!='\n')return ch;

else fun1();
}

Alexander
New poster
Posts: 5
Joined: Thu Dec 19, 2002 2:01 pm
Location: Moscow, Russia

### 112 (Tree Summing) Recursion?

Follows program gets WA! But why?
Maybe because of recursion? Too deep?
All my tests is working well... Help me please!

var
num,p,deep : integer;
ch : char;
ans,sign,a1,a2 : boolean;

function find(top:integer) : boolean;
var
root: integer;
begin
root:=0;
sign:=false;
inc(deep);
if (ch=')') then begin
find:=false;
end
else if (not ans) then begin
if (ch in ['-','+']) then begin
if ch='-' then sign:=true;
end;
while (ch in ['0'..'9']) do begin
root:=root*10+(ord(ch)-ord('0'));
end;
if sign then root:=root*-1;
a1:=find(root+top);
if not ans then a2:=find(root+top)
else a2:=true;

if (a1=a2) and (a1=false) and (root+top=num) then ans:=true;
find:=true;
end;
dec(deep);
end;

begin
while not eof do begin
ans:=false;
deep:=0;
find(0);
if ans then writeln('yes')
else writeln('no');
if ans and (not eoln) then readln;
end;
end.[/pascal]

hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

### Test cases for 112 (Tree Summing)?

I made a solution here, but I got WA for problem 112.
http://acm.uva.es/p/v1/112.html

Can anybody help me on this?

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

FILE	*fin = stdin;
int	L, limite;
char	string[20000];
int	index;

int		aceitavel(char c)
{
if(c == '(' || c == ')')
return 1;
else
if(c <= '9' && c >= '0')
return 1;
else
return 0;
}

int	recursao(int soma)
{
int	atual;
int	i1, i2;

if(string[index] == '(' && string[index+1] == ')')
{
index += 2;
return 0;
}

index++;

/* valor do no atual */
atual = atoi(&string[index]);

/* soma dos antecessores */
soma += atual;

while(string[index] != '(')
index++;

/* esquerda */
i1 = recursao(soma);
if(i1 == -1)
return -1;

/* direita */
i2 = recursao(soma);
if(i2 == -1)
return -1;

if(!i1 && !i2)
if(L == soma)
{
printf("yes\n");
return -1; /* sai da recursao */
}

index++;
return 1;
}

int	main()
{
int	parenteses = 0, i;
char	tmp;

/*	fin = fopen("treesum.txt", "r");	*/

while(fscanf(fin, " %d", &L) == 1)
{
i = 0;

while(fscanf(fin, "%c", &tmp) == 1 && aceitavel(tmp) == 0);

/* copia a string da arvore descartando chars inuteis */
do{
if(tmp == '(')
parenteses++;
else
if(tmp == ')')
parenteses--;

if(aceitavel(tmp) == 1)
string[i++] = tmp;

fscanf(fin, "%c", &tmp);
}while(parenteses);

string[i] = 0;

index = 0;
if(recursao(0) != -1)
printf("no\n");
}
}
``````
Thank you very much.