Page 8 of 10

#112 help plz

Posted: Sat Jul 23, 2005 5:57 pm
by 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;
}

Posted: Sun Jul 24, 2005 7:44 am
by 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

112 WA

Posted: Wed Oct 19, 2005 3:10 am
by 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!!!!

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

Posted: Wed Oct 19, 2005 3:15 am
by hongyan
There are nothing different between my output and yours.
I got WA. :cry: :cry: :cry:

Posted: Thu Oct 20, 2005 4:25 am
by 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?

112 WA

Posted: Sun Nov 06, 2005 3:37 am
by 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.

Posted: Sat Jan 14, 2006 6:54 pm
by 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;
}

Help:112

Posted: Sat Aug 05, 2006 11:35 am
by 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';
}

Posted: Thu Apr 05, 2007 3:39 pm
by 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

Posted: Sat Apr 28, 2007 8:16 pm
by nymo
Thanks to both of you... this IO set really helps me out...

Posted: Fri Aug 17, 2007 8:23 pm
by 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");
}
}

Posted: Fri Aug 17, 2007 8:30 pm
by emotional blind
to post code use 'Code' tag,
then your code will be more readable

Posted: Fri Aug 17, 2007 9:53 pm
by Mohsin Reza Razib
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");
}
}

Posted: Fri Aug 31, 2007 2:11 am
by 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.

Posted: Fri Aug 31, 2007 2:18 am
by 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