112 - Tree Summing

[komunist]

Help me please.
Where is my error?

var i,j,k,n,m,s,s1,s2:longint;
ch:char;
a :array [1..200000] of char;
b,c:array [1..200000] of longint;
f:boolean;

procedure push(a:longint);begin inc(s1);c[s1]:=a;s2:=s2+c[s1];end;
procedure pop; begin s2:=s2-c[s1];c[s1]:=0;dec(s1);end;

begin
while not eof do
begin
read(n);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
m:=0;k:=0;s:=0;s1:=0;s2:=1;
while true do
begin
read(ch);
if ch='-' then s2:=-1;
if ch='(' then begin inc(k);inc(s1);s2:=1;inc(m);a[m]:=ch;end;
if ch=')' then
begin
if a[m]='(' then begin a[m]:='#';dec(s1); end
else begin inc(m);a[m]:=')'; end;
dec(k);
end;
if ch in ['0'..'9'] then b[s1]:=b[s1]*10+s2*(ord(ch)-ord('0'));
if (m>0) and (k=0) then break;
end;
s1:=0;
s2:=0;
f:=false;
j:=0;
for i:=1 to m do
begin
if a='(' then begin inc(j);push(b[j]); end;
if a=')' then pop;
if a='#' then if s2=n then begin f:=true; break; end;
end;
if f=true then writeln('yes') else writeln('no');
end;
end.

[komunist]

HELP Please.

[shamim]

I get WA, my code passes all the input in the board. Please Help

[cpp]


CUT
[/cpp]

I found my mistake.

my program fails for cases like

1 ( 1 (0 ( 1 () () ) () ) () ) )

The answer should be "no".

[chunyi81]

Hi, try the following input:

input:
-3 (-1(-1()())(-2()()))

output:
yes

Hope this helps.

[Chocobo]

all above cases are OK but i still got WA...

[Skeeter]

Hi!
I`ve got some trouble with this problem. It looks to me like the Input isn`t described precisely in the target setting.
First of all, the integers might be positive, negativa and take 0 values, yes?
Then, is each test case terminaed with a '\n' symbol?
And two more questions: are the elements of the pare: integer , S-expression always devided by a space; Can a test case contain ' ' or '\n' symbols after the S-expression.
I use the cin.eof() function in my C++, I`m not sure it works on the tests.
Thaks a lot.

[efr_shovo]

112 Gives W.A. Why? Please Some Body Help Me.

please give me some Critican Input & Output

[emotional blind]

i think my program is ok.
but wa.
so i need some critical input and output.
can any body help me.
thanks.

[emotional blind]

my solution gets wa
can anyone help me ?

Code: Select all

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

char str[200000];
int summing (int num);
int main(void)
{
	int num, i, left, right;
	
	char c;
	while(scanf("%d",&num)==1){
		while((c=getchar())!='(');
		left=1;
		right=0;
		i=0;
		str[i++]=c;
		while(left!=right){
			c=getchar();
			if(isdigit(c) || c=='(' || c==')' || c=='-')str[i++]=c;
			if(c=='(')left++;
			else if(c==')')right++;
		}
		str[i]='\0';
		if(summing(num))printf("yes\n");
		else printf("no\n");
		
		
	}
	return 0;
}

int summing (int num)
{
	int stack[2000], top, left, right, i, j, sum, m=1;
	int leftC=1;
	top=0;
	i=1;
	left=1;
	right=0;
	
	while(right!=left){
		if(str[i]=='('){
			left++;
		}
		else if(str[i]==')'){
			right++;
			if(str[i-1]=='('){
				if(leftC)leftC=0;
				else{
					sum=0;
					for(j=0;j<top;j++)
						sum+=stack[j];
					if(sum==num)return 1;
					leftC=1;
				}
			}
			else if(str[i-1]==')'){
				top--;
				leftC=1;
			}
		}
		else if(str[i]=='-')m=-1;
		else{
			sum=0;
			sum+= str[i]-'0';
			while(isdigit(str[i+1])){
				i++;
				sum=sum*10+str[i]-'0';
			}
			stack[top++] = m*sum;
			m=1;
		}
		i++;
	}
	
	return 0;
}

it is my simple code
i used stack operation.

[ImLazy]

I think I'm in the same situation with Emotional Blind. My program works all right by the sample input while still gets WA by the on-line judge. I just need some special input to help me to debug. Anyone can help us?
This is my code:

Code: Select all

#include<stdio.h>
#define MAX 100
int main()
{
  int i,j,k,
      get,
      node[MAX],/*记录一条路径上的每个节点的值*/
      tree[MAX][2],/*每个结点上已经连上的结点数，每个结节点上有几个枝是空的*/
      sum,
      treesum,
      cntleft,cntright;
  char c;
  while(scanf("%d",&sum)==1)
  {
    for(i=0;i<MAX;i++)
    {
      node[i]=0;
      tree[i][0]=0;
      tree[i][1]=0;
    }
    i=0;
    j=-1;
    get=0;
    cntleft=0;
    cntright=0;
    do
    {
      while(1)
      {
        c=getchar();
        if(c==')')
          cntright++;
        if(c=='(')
        {
          cntleft++;
          break;
        }
      }
      j++;/*找到左括号了，树就向下走一层*/
      if(scanf("%d",&node[i])==1)
      {
        i++;
        continue;/*回到do,再开始找括号*/
      }
      else
      {
        j--;/*读不到数就回到上一层*/
        if(j>=0)/*如果是-1，说明根结点都没有，自然就结束了*/
        {
          tree[j][0]++;/*读不到数说明上一层的一枝已经到头了*/
          tree[j][1]++;/*且有一枝是空*/
        }
        if(j>=0 && tree[j][1]==2)/*两枝都空则找到一条路径*/
        {
          tree[j][0]=0;/*把这一层的枝数归零，以便自己另外一个兄第枝的计算*/
          tree[j][1]=0;
          j--;
          tree[j][0]++;
          treesum=0;
          for(k=0;k<i;k++)
            treesum+=node[k];
          if(treesum==sum)
          {
            get=1;
            break;
          }
          i--;/*回到上一层读另一枝读数*/
        }
        while(j>=0 && tree[j][0]==2)/*一直回溯到还没有两枝都满的那一层，重新找路径*/
        {
          tree[j][0]=0;
          tree[j][1]=0;
          j--;
          tree[j][0]++;
          i--;
        }
      }
    }while(tree[0][0]<2 && j>=0);/*根结点的两枝都满了，或都根结点为空，就结束了，*/
    while(cntleft!=cntright && cntleft!=0)/*把这一次输入剩下的那些东西都吃光*/
    {
      c=getchar();
      if(c==')')
        cntright++;
      if(c=='(')
        cntleft++;
    }
    if(get==1)
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}

[ImLazy]

Dear Mistr,
My program works all right by the inupts you have given above, but still WA!!! I'm getting crazy!

[masumasu]

#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>

using namespace std;

class linkedlist
{
public:
int value;
char *path;
linkedlist *next;
};
class linkhead
{
public :
int level;
linkedlist *next;

linkhead()
{
next = NULL;
}
};
linkhead **tree;

void displaytree(int treeheight)
{
for (int i=0;i<=treeheight;i++)
{
linkedlist *p = tree[i]->next;
while (p!=NULL)
{
cout << p->value << " " << p->path << " ";
p = p->next;
}
cout << endl;
}
}

void putnodevalue(int nodevalue,char* path,int level)
{
if (tree[level]->next==NULL)
{
//cout << " Null here ...\n";
tree[level]->next = new linkedlist();
tree[level]->next->next = NULL;
tree[level]->next->value = nodevalue;
tree[level]->next->path = new char[strlen(path)+1];
strncpy(tree[level]->next->path,path,level);
//tree[level]->next->path[level+1] = 0;
tree[level]->next->path[level+1] = 0;
return ;
}

//cout << " not Null here ...\n";
linkedlist *p = tree[level]->next;
while (p->next!=NULL)
p = p->next;

p->next = new linkedlist();
p->next->value = nodevalue;
p->next->next = NULL;
p->next->path = new char[strlen(path)+1];
strncpy(p->next->path,path,level);
p->next->path[level+1] = 0;

p = tree[level]->next;
/*while (p!=NULL)
{
cout << p->value << " "<< p->path <<" ";
p=p->next;
}
cout << endl;*/
return ;
}

bool presentstring(char *s1,char *s2,int number)
{
if (number==0)
return true;
for (int i=0;i<number-1;i++)
if (s1[i]!=s2[i])
return false;
return true;
}
bool presentsum(int reqdsum,int treeheight,int currlevel,char *path)
{

if (tree[currlevel]->next==NULL)
{
//cout << "Here...\n";
if (( currlevel==0) || (reqdsum!=0))
return false;
else
return true;
}
linkedlist *p = tree[currlevel]->next;
while (p!=NULL)
{
//cout << "Came here...\n";
if (presentstring(p->path,path,currlevel))
{
//cout << "True";
if (presentsum(reqdsum - p->value,treeheight,currlevel+1,p->path))
{
return true;
}
}
p = p->next;
}

return false;

}
int main()
{
char c;
char path[105];
int reqdsum,treelevel = 0,valuesign,treeheight=-1;
bool lefttree;

//strcpy(path,"222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");

//strcpy(path,"22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");

while (cin >> reqdsum)
{
tree = new linkhead*[105];
for (int i=0;i<105;i++)
tree[i] = new linkhead();
while ((c=getchar())!='(')
{
}
//getchar();
//getchar();

lefttree = true;
treelevel = 0;
int nodevalue = 0;
valuesign = 1;
treeheight = -2;
//strcpy(path,"22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");
for (int i=0;i<105;i++)
path[i]='2';

while ( (treelevel>=0) and ( (c=getchar())!=EOF ) )
{
if ((c==' ') || (c=='\n'))
{
continue;
}
if (c=='-')
{
valuesign = -1;
}

if ((c>='0') and (c<='9'))
{
do
{
nodevalue = nodevalue * 10 + (c-'0')* valuesign;
c=getchar();
}while ((c>='0') and (c<='9'));

putnodevalue(nodevalue,path,treelevel);
//cout << nodevalue << " " << treelevel << endl;
//cout << path << endl;
ungetc(c,stdin);
nodevalue=0;
valuesign = 1;
if (treeheight<treelevel)
treeheight = treelevel;
continue;
}
if ( c=='(')
{
//treelevel++;
//if (treelevel==-1)
// treelevel++;
if (path[treelevel]=='2')
{
path[treelevel]='0';
}
else if (path[treelevel]=='0')
path[treelevel]='1';
treelevel++;

}
else if (c==')')
{
if (treelevel>=0)
{
path[treelevel]='2';
treelevel--;
}
}

}
//if (tree[0]->next==NULL)
/// cout << "Tree Null no\n";
// else
if (presentsum(reqdsum,treeheight,0,""))
cout << "yes\n";
else
cout << "no\n";
//displaytree(treeheight);
/*while ((c=getchar())!=EOF)
if (( (c>='0') and (c<='9') ) or (c=='-') )
break;
ungetc(c,stdin); */
//cout << endl;
//for (int i=0;i<1000;i++)
// delete []tree;

//delete tree;
}
}

[teni_teni]

Though I don't look into your code, try this input:

Code: Select all

3
(1
  (1 (1 ()()) ())
  (2 ()       ())
)

3
(1
  (1 (2 ()()) ())
  (2 ()       ())
)

[masumasu]

hi thans to u
even though i cant figure out how u got that input for which my prog didnt work ......... i corrected it and its accepted now.........
again thans

[ImLazy]

I think the output should be:

Code: Select all

yes
yes

My code works all right for the input above, but still WA.

Code: Select all

#include<stdio.h>
#define MAX 100
int main()
{
  struct node
  {
    int value;
    int visit;
    struct node *parent,*left,*right;
  }tree[MAX],*p,*temp;
    int n,
        get,
        sum,
        treesum,
        cnt_left,cnt_right,
        cnt_node,
        i;
  char c;
  while(scanf("%d",&sum)==1)
  {
    for(i=0;i<MAX;i++)
    {
      tree[i].visit=0;
      tree[i].parent=NULL;
      tree[i].left=NULL;
      tree[i].right=NULL;
    }
    get=0;
    cnt_left=0;
    cnt_right=0;
    cnt_node=0;
    p=&tree[0];
    p->parent=NULL;
    do
    {
      while(1)
      {
        c=getchar();
        if(c==')')
          cnt_right++;
        if(c=='(')
        {
          cnt_left++;
          break;
        }
      }
      if(scanf("%d",&n)==1)
      {
        p->value=n;
        cnt_node++;
        p->left=&tree[cnt_node];
        p->left->parent=p;
        cnt_node++;
        p->right=&tree[cnt_node];
        p->right->parent=p;
        p=p->left;
        continue;/*回到do,再开始找括号*/
      }
      else if(p->parent!=NULL)
      {
        p=p->parent;
        p->visit++;
        if(p->visit==1)
        {
          p->left=NULL;
          p=p->right;
        }
        else if(p->visit==2)
        {
          p->right=NULL;
          if(p->visit==2 && p->left==NULL)
          {
            treesum=p->value;
            temp=p;
            while(temp->parent!=NULL)
            {
              temp=temp->parent;
              treesum+=temp->value;
            }
            if(treesum==sum)
            {
              get=1;
              break;
            }
          }
          while(p->parent!=NULL && p->visit==2)/*一直回溯到两枝还没有走完的那一层*/
          {
            p=p->parent;
            p->visit++;
          }
          if(p->visit==1)
            p=p->right;
        }
      }
    }while(tree[0].visit<2 && (tree[0].left!=NULL || tree[0].right!=NULL));
    /*最顶层的两枝都满了，或两枝都空就结束了*/
    while(cnt_left!=cnt_right && cnt_left!=0)/*把这一次输入剩下的那些东西都吃光*/
    {
      c=getchar();
      if(c==')')
        cnt_right++;
      if(c=='(')
        cnt_left++;
    }
    if(get==1)
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}