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

komunist
New poster
Posts: 4
Joined: Thu Mar 11, 2004 3:20 pm

### 112 WA WHY

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
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
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
New poster
Posts: 4
Joined: Thu Mar 11, 2004 3:20 pm

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### 112 Tree Summing( WA)

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".
Last edited by shamim on Wed Jun 02, 2004 10:37 am, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Hi, try the following input:

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

output:
yes

Hope this helps.

Chocobo
New poster
Posts: 2
Joined: Sat Jul 24, 2004 5:25 am
all above cases are OK but i still got WA...

Skeeter
New poster
Posts: 1
Joined: Wed Aug 18, 2004 12:21 pm
Contact:

### WA

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
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 112 Why W.A

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

please give me some Critican Input & Output
Last edited by efr_shovo on Mon Sep 27, 2004 5:51 am, edited 1 time in total.

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

### problem with 112

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

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

### 112 gets wa

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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### ...

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;
}``````
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### ...

Dear Mistr,
My program works all right by the inupts you have given above, but still WA!!! I'm getting crazy!
I stay home. Don't call me out.

masumasu
New poster
Posts: 3
Joined: Thu Dec 09, 2004 3:06 pm

### 112 WA Please help me.....Wrked for all the test cases given

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

using namespace std;

{
public:
int value;
char *path;
};
{
public :
int level;

{
next = NULL;
}
};

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)
{
for (int i=0;i<105;i++)
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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am
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
New poster
Posts: 3
Joined: Thu Dec 09, 2004 3:06 pm
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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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;
}``````
Last edited by ImLazy on Thu Feb 17, 2005 7:08 am, edited 1 time in total.
I stay home. Don't call me out.