## 112 - Tree Summing

Moderator: Board moderators

shuvic
New poster
Posts: 1
Joined: Sat Jul 23, 2005 5:52 pm

### #112 help plz

i cannot understand this code is waaaaaaaaaaaaaaa..

help me plz

Code: Select all

``````#include <iostream>
#include <stack>

using namespace std;

int main()
{
int num;
char tmpChar[6];
int tmpPos, tmp;
int bracketCount;
int sum;
bool flg, bracketFlag;
stack<int> st;

while(cin >> num)
{
bracketCount=0;
sum=0;
tmpPos=0;
flg=false;
bracketFlag=false;

do {
cin >> tmpChar[tmpPos];

if (tmpChar[tmpPos]=='(')
{
tmpChar[tmpPos]=0;
++bracketCount;

if (tmpPos)
{
tmp=atoi(tmpChar);
st.push(tmp);
sum+=tmp;
}
st.push(0);		// insert bracket

tmpPos=0;
}
else if (tmpChar[tmpPos]==')')
{
tmpChar[tmpPos]=0;
--bracketCount;

if (tmp=st.top())
{
while(tmp)
{
sum-=tmp;
st.pop();
tmp=st.top();
}
bracketFlag=false;
}
else
{
if (bracketFlag)
{
flg=flg | (sum==num);
bracketFlag=false;
}
bracketFlag=true;
}
st.pop();		// delete bracket
}
else
++tmpPos;

} while(bracketCount);

if (flg)
cout << "yes" << endl;
else
cout << "no" << endl;
}

return 0;
}``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
The leaf must not have any successor
and all sum should be calculated
from root to leaf

look at this inputs
INPUT

Code: Select all

``````10 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )
10 (5 () (5 () (5 () (5 ( 3 () () ) (4 () () ) ) ) ) )
20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) )``````
The output of this set of inputs should be
OUTPUT

Code: Select all

``````no
no
no``````
OUTPUT (Wrong)

Code: Select all

``````yes
yes
yes``````
check thease carefully

hongyan
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu

### 112 WA

I have read all the topic about 112,and try all the data correct.I don't know why still wrong answer. Anyone can help me?Thanks a lot!!!!

Here is my code:

Code: Select all

``````#include<stdio.h>
const long maxn=10000;
char ch,s[maxn+5];
long l,n,m,sz[maxn+5],tree[maxn+5],leaf[maxn+5];

long run(long x){
long tot,p,i;
tot=0;p=tree[x];
for (i=x;i>0;i--){
if (tree[i]==p){
tot+=sz[i];p=p/2;
}
}
}

int main()
{
long te,i,j,p,mark,bj;
while(scanf("%ld",&n)!=EOF)
{
scanf("%c",&ch);while (ch!='(') scanf("%c",&ch);
te=1;l=0;
while (te>0){
scanf("%c",&ch);
if (ch>='0'&&ch<='9'||ch=='('||ch==')'||ch=='-'){
l++;s[l]=ch;
if (ch=='(') te++;
else if (ch==')') te--;
}
}
p=1;i=1;m=0;
while (p>0&&i<=l){
if (s[i]>='0'&&s[i]<='9'||s[i]=='-'){
te=0;mark=0;
if (s[i]=='-'){
i++;mark=1;
}
while (s[i]>='0'&&s[i]<='9'){
te=te*10+s[i]-'0';i++;
}
m++;sz[m]=te;
if (mark) sz[m]=-sz[m];
tree[m]=p;
if (i+3<=l&&s[i]=='('&&s[i+1]==')'&&s[i+2]=='('&&s[i+3]==')') leaf[m]=1;
else leaf[m]=0;
}else{
if (s[i]=='('){
i++;p=p*2;bj=1;
for (j=1;j<=m&&bj;j++){
if (tree[j]==p) bj=0;
}
if (!bj) p++;
}else{
p=p/2;i++;
}
}
}
if (m==0) printf("no\n");
else{
bj=1;
for (i=m;i>0&&bj;i--){
if (leaf[i]&&run(i)==n) bj=0;
}
if (!bj) printf("yes\n");
else printf("no\n");
}
}
return 0;
}
``````

hongyan
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu
There are nothing different between my output and yours.
I got WA.

hongyan
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu
I don't know whether it wrong because I consider the left child node and right child node as the same.

when I make the tree, for each father node, I put the child node on the left first, and then fill the right node.

I think it's right. But I got WA.Maybe my algorithm is wrong?
my QQ number is 76296127
welcome for connect me!!

shiqicao
New poster
Posts: 1
Joined: Sun Nov 06, 2005 3:34 am

### 112 WA

Code: Select all

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

int size;
int found;

void getC(char c){
while(getchar() != c );
}

int findPath(int n){
int node,n1,n2;
getC('(');
if (scanf("%d",&node)){
size++;
n1=findPath(n - node);
n2=findPath(n - node);
if (!(n1 || n2) && n == node)
found = 1;
return 1;
}
else {
getC(')');
return 0;
}
}

int main(){
int sum;
char t[100];
while (scanf("%d",&sum)){
found = size = 0;
findPath(sum);
if ( found && size){
printf ("yes\n");
}else{
printf ("no\n");
}
scanf ("%[^\n]*s",t);
}
}``````
I tested a lot of cases, but still got WA.
CAO Shiqi

New poster
Posts: 8
Joined: Wed Mar 30, 2005 9:46 am
I got an AC. Here is my code: ( hope that it helps )

#include <iostream>
#include <stack>

using namespace std;

int main()
{
int n;
stack<int> s;

while(cin>>n)
{
bool yes=false;
bool lchild=false;
char c;
do{
cin>>c;
while(c==' '||c=='\t'||c=='\n') cin>>c;
if(c=='(')
{
//push
char test;
int t;
cin>>test;
if((test>='0'&&test<='9')||test=='-')
{
lchild=false;
cin.unget();
cin>>t;
s.push(t);
n-=t;
}
else
//leaf?
{
if(lchild)
if(n==0) yes=true;
lchild=true;
}
}else if(c==')')
{
//pop
lchild=false;
n+=s.top();
s.pop();
}
}while(!s.empty());
if(yes) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}

return 0;
}

doris_wei
New poster
Posts: 1
Joined: Sat Aug 05, 2006 11:32 am

### Help:112

Why do I got RE?Thank you!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Input();
void Oprate(int std);

char info[30000],bracket[10000];
int stack[10000];

int main()
{
int std;
while( scanf( "%d" , &std ) != EOF )
{
Input();
Oprate(std);
}
return 1;
}

void Oprate(int std)
{
unsigned int i,len = strlen(info);
int si = -1;
char number[15];
int sum = 0;

for( i = 0 ; i < len ; i++ )
{
if( info == '(' )
{
if( info[i+1] == ')' )
if( info[i+2] == '(' && info[i+3] == ')' )
if( sum == std )
{
printf( "yes\n" );
return;
}
else
i += 3;
else
i++;
else
{
int num;
memset(number,0,15*sizeof(char));
char j = i+1 , k = 0;
while( info[j] != ')' && info[j] != '(' )
number[k++] = info[j++];
if( info[j] == ')' )
i = j;
else if( info[j] == '(' )
i = j-1;
num = atoi(number);
sum += num;
stack[++si] = num;
}

}
else
{
sum -= stack[si];
si--;
}

}

printf( "no\n" );

}

void Input()
{
char ch,tag = 0,bi = -1,i = 0;

while(1)
{
if( bi == -1 && i != 0 )
break;
ch = getchar();
if( ch == '(' || ch == ')' || ( ch >= '0' && ch <= '9' ) || ch == '-' )
info[i++] = ch;

if( ch == '(' )
bracket[++bi] = '(';
else if( ch == ')' )
bi--;
}
info = '\0';
}

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
My AC'ed program gives following output

Code: Select all

``````yes
no
yes
no
no
yes
no
yes
yes
no
yes
yes
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
yes
yes
yes``````
I guess such an input

Code: Select all

``````5 ( 5 () 1 () ())
4 ( 2 (2 () 1()()) ()) ``````
isn't correct, it doesn't follow the input specification
Hope it helps
keep it real!

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
Thanks to both of you... this IO set really helps me out...
regards,
nymo

Mohsin Reza Razib
New poster
Posts: 12
Joined: Fri Dec 15, 2006 12:57 pm
Contact:
I am getting the message :
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
This is my code. Someone plz tell me why i am having this problem. The program seems ok to me.
CODE:
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
void main(){
int a[10000],b,i=0,j,max,n,ter,sum,indx,neg,mk[10000];
char ch,s1[10000];
while(scanf("%d ",&n)==1)
{
ter=0;indx=1; max=0;b=0;
for(i=0;i<10000;i++)
{a=0; mk=0;}
i=0;
s1[0]='\0';
neg=1;
while(1)
{
scanf("%c",&ch);
if(ch=='(')
{ter++;s1='\0';i=0;
}
if(ch==')')
{ter--;s1='\0';i=0;}
if(ch=='-')
neg=-1;
if(isdigit(ch))
{
s1=ch;i++;
}
if(ch=='(')
{
if(s1[0]!='\0'&&mk[indx]!=1)
{ mk[indx]=1;a[indx]=neg*atoi(s1);
}
neg=1;
}
if(ch=='('&&a[1]!=0)
{
if(mk[indx*2]==0)
indx*=2;
else if(mk[indx*2]!=0)
indx=indx*2+1;
}
if(ch==')')
{
if(s1[0]=='\0'&&mk[indx]!=1&&indx!=1)
{a[indx]=0;mk[indx]=1;}
indx=indx/2;
}
if(max<indx)
max=indx;
if(ter==0)
break;
}
for(i=max,b=0;i>=1;i--)
{
if(a[i*2]==0&&a[i*2+1]==0&&a!=0)
{
sum=0;
for(j=i;j>=1;)
{
sum+=a[j];
j=j/2;
}
if(sum==n)
{ b=1;
printf("Yes");
break;
}
}
}
if(b==0)
printf("No");
printf("\n");
}
}
Mohsin Reza
"The tragedy of life does not lie in not reaching your goal. The tragedy lies in having no goal to reach".- Benajamin Mays

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
to post code use 'Code' tag,

Mohsin Reza Razib
New poster
Posts: 12
Joined: Fri Dec 15, 2006 12:57 pm
Contact:
Mohsin Reza Razib wrote:I am getting the message :
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
This is my code. Someone plz tell me why i am having this problem. The program seems ok to me.
CODE:
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
void main(){
int a[10000],b,i=0,j,max,n,ter,sum,indx,neg,mk[10000];
char ch,s1[10000];
while(scanf("%d ",&n)==1)
{
ter=0;indx=1; max=0;b=0;
for(i=0;i<10000;i++)
{a=0; mk=0;}
i=0;
s1[0]='\0';
neg=1;
while(1)
{
scanf("%c",&ch);
if(ch=='(')
{ter++;s1='\0';i=0;
}
if(ch==')')
{ter--;s1='\0';i=0;}
if(ch=='-')
neg=-1;
if(isdigit(ch))
{
s1=ch;i++;
}
if(ch=='(')
{
if(s1[0]!='\0'&&mk[indx]!=1)
{ mk[indx]=1;a[indx]=neg*atoi(s1);
}
neg=1;
}
if(ch=='('&&a[1]!=0)
{
if(mk[indx*2]==0)
indx*=2;
else if(mk[indx*2]!=0)
indx=indx*2+1;
}
if(ch==')')
{
if(s1[0]=='\0'&&mk[indx]!=1&&indx!=1)
{a[indx]=0;mk[indx]=1;}
indx=indx/2;
}
if(max<indx)
max=indx;
if(ter==0)
break;
}
for(i=max,b=0;i>=1;i--)
{
if(a[i*2]==0&&a[i*2+1]==0&&a!=0)
{
sum=0;
for(j=i;j>=1; )
{
sum+=a[j];
j=j/2;
}
if(sum==n)
{ b=1;
printf("Yes");
break;
}
}
}
if(b==0)
printf("No");
printf("\n");
}
}
Mohsin Reza
"The tragedy of life does not lie in not reaching your goal. The tragedy lies in having no goal to reach".- Benajamin Mays

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
Contact:
My program gives the same output as given above for all cases, except for the last 2 cases, which as specified above are not valid inputs:-

Code: Select all

``````5 ( 5 () 1 () ())
4 ( 2 (2 () 1()()) ())
``````
But I am still getting WA

What should be the output for:

Code: Select all

``0 ()``
BTW, I have submitted my code by printing both yes and no for the above case. Its still WA. Bug is at some other place.

sandy007smarty
New poster
Posts: 20
Joined: Thu Apr 20, 2006 6:55 pm
``0 ()``
``no``