112 - Tree Summing

[shuvic]

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]

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

but your output give
OUTPUT (Wrong)

Code: Select all

yes
yes
yes

check thease carefully

[hongyan]

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

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]

There are nothing different between my output and yours.
I got WA.

[hongyan]

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?

[shiqicao]

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.

[gladiatorcn]

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]

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]

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

[nymo]

Thanks to both of you... this IO set really helps me out...

[Mohsin Reza Razib]

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

[emotional blind]

to post code use 'Code' tag,
then your code will be more readable

[Mohsin Reza Razib]

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

[sandy007smarty]

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]

I just got AC with my same old code. I don't know why it give WA earlier. May be I submitted the wrong version.

BTW, for the test case:

Code: Select all

0 ()

my AC code prints:

Code: Select all

no