112 - Tree Summing

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

Moderator: Board moderators

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

#112 help plz

Post by shuvic » Sat Jul 23, 2005 5:57 pm

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Jul 24, 2005 7:44 am

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
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu

112 WA

Post by hongyan » Wed Oct 19, 2005 3:10 am

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!!!!

:cry: :cry: :cry:


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
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu

Post by hongyan » Wed Oct 19, 2005 3:15 am

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

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

Post by hongyan » Thu Oct 20, 2005 4:25 am

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?
please call me hongyan.
my QQ number is 76296127
my Email address is sanwushuosi@163.com
welcome for connect me!!

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

112 WA

Post by shiqicao » Sun Nov 06, 2005 3:37 am

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

gladiatorcn
New poster
Posts: 8
Joined: Wed Mar 30, 2005 9:46 am

Post by gladiatorcn » Sat Jan 14, 2006 6:54 pm

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

Post by doris_wei » Sat Aug 05, 2006 11:35 am

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

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Thu Apr 05, 2007 3:39 pm

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

Post by nymo » Sat Apr 28, 2007 8:16 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Mohsin Reza Razib » Fri Aug 17, 2007 8:23 pm

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Fri Aug 17, 2007 8:30 pm

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

Mohsin Reza Razib
New poster
Posts: 12
Joined: Fri Dec 15, 2006 12:57 pm
Location: Dhaka, Bangladesh
Contact:

Post by Mohsin Reza Razib » Fri Aug 17, 2007 9:53 pm

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
Location: Hyderabad
Contact:

Post by sandy007smarty » Fri Aug 31, 2007 2:11 am

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
Location: Hyderabad
Contact:

Post by sandy007smarty » Fri Aug 31, 2007 2:18 am

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

Post Reply

Return to “Volume 1 (100-199)”