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

Innovative Cat
New poster
Posts: 1
Joined: Sun Jul 28, 2002 8:23 am
Location: China
Contact:

[b]Help! Problem 112. Wrong Answer!!!!!!![/b]

Post by Innovative Cat »

:cry:
[pascal]
Program P112_Tree_Summing;
Var
t : String;
Aim : Integer;
Ch : Char;
Procedure GetChar(var ch:Char);
Begin
Read(Ch);
While Not Eof(input) And
(Ch<>'(') And
(Ch<>')') And
(Ch<>'-') And
(Ch<>'+') And
((Ch>'9') Or
(Ch<'0')) Do Read(Ch);
End;
Function Find(Sum:Integer):Byte;
Var
x,y,Num : Integer;
Begin
GetChar(Ch);
If Ch=')' Then Begin
GetChar(Ch);
Find:=2;
Exit;
End;
t:='';
While Ch<>'(' Do
Begin
t:=t+Ch;
GetChar(Ch);
End;
Val(t,Num,Num);
Inc(Sum,Num);
x:=Find(Sum);
y:=Find(Sum);
If (x=0) Or (y=0) Or
((x=2) And (y=2) And (Sum=Aim))
Then Find:=0
Else Find:=1;
GetChar(Ch);
End;
Begin
GetChar(ch);
While Not Eof(Input) Do
Begin
t:='';
While Ch<>'(' Do
Begin
t:=t+Ch;
GetChar(Ch);
End;
If Eof(Input) Then Break;
Val(t,Aim,Aim);
If Find(0)=0
Then Writeln('yes')
Else Writeln('no');
End;
End.
[/pascal][/code]

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

112 SIGSEGV

Post by pc5971 »

I received the answer

"Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference"

to my programme and I can't see way...


[pascal]
program p112(input,output);
type pnod=^nod;
nod=record
nr:integer;
st,dr:pnod;
end;

var rad:pnod;
s:string;
p,nr:integer;

procedure tree(var rad:pnod;var p:integer);
var n:integer;
begin
if s[p+1]=')' then
begin
rad:=NIL;
p:=p+1;
end
else
begin
n:=0;
p:=p+1;
while s[p] in ['0'..'9'] do
begin
n:=n*10+ord(s[p])-ord('0');
p:=p+1;
end;
new(rad);
rad^.nr:=n;
tree(rad^.st,p);
p:=p+1;
tree(rad^.dr,p);
p:=p+1;
end;
end;

function verif(s:integer; rad:pnod):boolean;
begin
if rad=NIL then
if s=0 then
verif:=true
else
verif:=false
else
verif:=verif(s-rad^.nr,rad^.st) or verif(s-rad^.nr,rad^.dr);
end;
procedure sterg(var s:string);
var i:integer;
begin
i:=pos(' ',s);
while i<>0 do
begin
delete(s,i,1);
i:=pos(' ',s);
end;
end;

procedure numara(s:string;var n1,n2:integer);
var i:integer;
begin
for i:=1 to length(s) do
if s='(' then
n1:=n1+1
else
if s=')' then
n2:=n2+1;
end;


procedure citire(var s:string; var nr:integer);
var i,cod:integer;
s1:string;
n1,n2:integer;
begin
readln(s);
while s[1]=' ' do
delete(s,1,1);
while s[length(s)]=' ' do
delete(s,length(s),1);
i:=pos(' ',s);
if i=0 then
begin
val(s,nr,cod);
s:='';
end
else
begin
s1:=copy(s,1,i-1);
val(s1,nr,cod);
delete(s,1,i);
sterg(s);
end;
n1:=0; n2:=0;
numara(s,n1,n2);
while (n1<>n2) or ((n1=n2) and (n1=0)) do
begin
readln(s1);
sterg(s1);
numara(s1,n1,n2);
insert(s1,s,length(s)+1);
end;
end;

procedure destroy(var rad:pnod);
begin
if rad<>NIL then
begin
destroy(rad^.st);
destroy(rad^.dr);
dispose(rad);
rad:=NIL
end;
end;

begin
while not eof(input) do
begin
citire(s,nr);
p:=1;
tree(rad,p);
if verif(nr,rad) then
writeln('yes')
else
writeln('no');
destroy(rad)
end;
end.
[/pascal]

Can you help me???

Thanks

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

Annoying Runtime Error

Post by 1_UtterBlue »

Sorry I didn't take a close look on your programme. But, as far as I know, dividing by 0 or trying to manipulate the pointer which is assigned NIL would usually lead to Runtime Error. Try to enlarge your array or something like that.
James.Hao (Bonjour!)

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan

112 -Tree Summing [runtime-error](SIGSEGV)

Post by ywliu »

i don't find where run-time error....
who can tell me why..

[cpp]
#include<iostream>
#include<string>
#include<queue>
using namespace std;

queue<int> qu;
string sData="";
int start=0;
int rightx=0;
int tree_length=0;
int *position;

void input_data();
void run(string s1);
void cut(string s1);
int check(string s1);
void main(){
input_data();
}
void input_data(){
string sBuff;
while(!cin.eof()){
getline(cin,sBuff);
if(sBuff=="")continue;
cut(sBuff);
if(check(sData)==1 && sData.find('(',0)!=-1){
long value;
value = atol( sData.substr( 0,sData.find('(',0)-0).c_str() );
rightx++;
run( sData.substr( sData.find('(',0)+1 , sData.length() ) );
sData="";
start=0;
int yes=0;
position = new int[tree_length];
while(qu.size()!=0){
int k1,k2,k3;
k1=qu.front();
qu.pop();
k2=qu.front();
qu.pop();
if(k2>0)
position[k2-1]=k1;
else{
position[-1*k2-1]=k1;
long cost=0;
for(k3=0;k3<-1*k2;k3++)
cost+=position[k3];
if(value==cost){
yes=1;
break;
}
}
}
tree_length=0;
delete position;
if(yes==1) cout << "yes" << endl;
else cout << "no" << endl;
}
}
}
void run(string s1){
int k1;
for(k1=0;k1<s1.length();){
if( s1.at(k1)=='('){
rightx++;
k1++;
}
else if( s1.at(k1)==')'){
rightx--;
k1++;
}
else{
long node;
node = atol( s1.substr( k1,s1.find('(',k1)-k1).c_str() );
k1=s1.find('(',k1);
qu.push( node );
if( s1.substr( k1 , 4 )=="()()" ){
if(tree_length < rightx) tree_length = rightx;
qu.push(-1*rightx);
k1+=4;
}
else
qu.push( rightx );
}
}
}
void cut(string s1)
{
int p,q;
q=0;
p=s1.find(" ");
for(;p!=-1;){
if(p!=q)
sData+=s1.substr(q,p-q);
q=p+1;
p=s1.find(" ",p+1);
}
p=s1.length();
if(p!=q)
sData+=s1.substr(q,p-q);
}
int check(string s1){
int k1;
for(k1=start;k1<s1.length();k1++){
if(s1.at(k1)=='(') rightx++;
else if(s1.at(k1)==')')
rightx--;
}
start=s1.length();
if(rightx!=0) return 0;
else return 1;
}
[/cpp]

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

WA 112...

Post by Archangel »

I have test as many case(negative number,empty tree) as I can, but still get WA, can anybody help me?

Code: Select all

/* problem 112 C++ */
#include<iostream.h>
#include<vector>

char cursor,sign,precursor;
int  num,query,i,j,sum,level;
bool result;

using namespace std;

void main(void)
{	
	vector<int> numlv;
	vector<int> number;
	while(cin>>query)
	{
		cin>>cursor; /* read in first "(" */
		level = 1;
		/* read in one case of input */
		while (level != 0) 
		{
			cin>>cursor;
			if ((cursor != ')')&&(cursor != '('))
			{
				if (cursor == '-')
				{
					sign = '-';
					cin>>cursor;
				}
				else
					sign = '+';
				num = 0;
				while ((cursor > 47)&&(cursor < 58))
				{
					if (num == 0)
						num = cursor - 48;
					else
						num = num * 10 + cursor - 48;
					cin>>cursor;
				}				
				if (sign == '+')
					number.push_back(num);
				else
					number.push_back(0-num);
				numlv.push_back(level);
				level++;
			}
			else if (cursor == ')') /* read in ")" */
			{
				if (precursor == '(')
				{
					number.push_back(0);
					numlv.push_back(0);
				}				
				level--;
			}
			else /* read in "(" */
				level++;		
			precursor = cursor;
		}				
		if (number.size() == 0) /* when null tree occurred */
			cout<<"no\n";
		else
		{
			result = false;
			for (i=0;i<number.size()-2;i++)
			{
				sum = 0;
				if ((numlv[i] != 0)&&(numlv[i+1] == 0)&&(numlv[i+2] == 0))
				{
					level = numlv[i];
					for (j=i;j>=0;j--)
					{
						if (numlv[j] == level)
						{
							sum = sum + number[j];
							if (level == 1)
								break;
							level--;
						}
					}
				}
				if (sum == query)
					result = true;
			}
			if (result == true)
				cout<<"yes\n";
			else
				cout<<"no\n";
		}		
		number.clear();
		numlv.clear();
	}	
}


Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

112

Post by Master »

[/b] How many leaf to root path is in the following tree

22 (5(10()(20))(10()())) :roll:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

I think that's incorrect input data ...
Maybe it should be

Code: Select all

22 (5(10()(20()()))(10()()))  
??

Dominik

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

Is it a binary tree? :roll:
why you put those blank leaves after 20? :-?
ImageWe are all in a circular way, no advances, only moving and moving!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

If I should remember it should be binary tree ...
But I can made a mistake ;-)
Grammas,which is given to this problem, says that's binary tree ...

Dominik

luzi82
New poster
Posts: 4
Joined: Wed Oct 16, 2002 3:18 pm

if you find 112 is difficult............

Post by luzi82 »

think of the negative input

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Give me the test,please

Post by nghiank »

test
Last edited by nghiank on Sun Apr 22, 2007 3:41 pm, edited 1 time in total.

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX »

to problem 112:

input:
9 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
output:
no


I think you might have bug here.

User avatar
Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm

P 112: Why WA? :o

Post by Angel »

I've considered negetive case...empty tree....but still WA.

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


char fun1();
signed long int Sum[15000],count=-1,countf=0,flagf=0,countob=1,countcb=0,flagclose=0;
void main(void)
{
freopen("h:\\tc\\testing\\f1.in" , "r",stdin);
signed long int sum=0,s=0,s1,input,first,flag=0,flag2=0,flags=0,count2=0,count3=0,ritu=0;
char cath;
while(scanf("%ld",&first)==1)
{
flagclose=0;
while(countob>countcb&&flagclose==0)
{
ritu++;
if(ritu==1){countob=0;countcb=0;}
cath=fun1();
if(ritu==1){if(cath==' '||cath=='\n'){ritu=0;countob=1;countcb=0;}}
if(cath=='(')
{
flags=0;
if(scanf("%ld",&input)==1)
{
Sum[s++]=input;
count3=0;
}
else count3++;
}
else if(cath==')')
{
count2++;
if(count3==2&&count2==3){count-=3;count2-=3;for(s1=0;s1<s;s1++){sum+=Sum[s1];flag2=1;}}
if(sum==first)
{
sum=0;
flag=1;
}
}
sum=0;
if(flag2==1){Sum[s-1]=0;flag2=0;count3=0;flags=1;s=s-1;}
if(flags==1&&count2==1){Sum[s-1]=0;s=s-1;flags=0;count-=1;count2=0;}
if(count==count2){for(s1=1;s1<s;s1++)Sum[s1]=0;count=0;count2=0;}
if(flag!=1&&cath=='e')
{
printf("no\n");
memset(Sum,0,sizeof(Sum)-1);
count=-1;countf=0;flagf=0;countob=1;countcb=0;flag=0;flag2=0;count2=0;count3=0;
sum=0;s=0;ritu=0;
flagclose=1;
}
if(flag==1&&cath=='e')
{
printf("yes\n");
memset(Sum,0,sizeof(Sum)-1);
count=-1;countf=0;flagf=0;flag=0;flag2=0;count2=0;count3=0;
sum=0;s=0;
flagclose=1;
}
}
countob=1;countcb=0;ritu=0;
}
}

char fun1()
{
char ch;
scanf("%c",&ch);
countf++;
if(ch=='(')countob++;
if(ch==')')countcb++;
if(countf==2){if(ch=='('){count++;flagf=1;} }
else if(flagf==1)if(ch=='('){count++;}
if(countob!=0&&countcb!=0&&countob==countcb)return 'e';
else if(ch!=' '||ch!='\n')return ch;

else fun1();
}

Alexander
New poster
Posts: 5
Joined: Thu Dec 19, 2002 2:01 pm
Location: Moscow, Russia

112 (Tree Summing) Recursion?

Post by Alexander »

Follows program gets WA! But why?
Maybe because of recursion? Too deep?
All my tests is working well... Help me please!

[pascal]program task112;
var
num,p,deep : integer;
ch : char;
ans,sign,a1,a2 : boolean;

function find(top:integer) : boolean;
var
root: integer;
begin
root:=0;
sign:=false;
inc(deep);
if (ch=')') then begin
find:=false;
read(ch);
end
else if (not ans) then begin
if (ch in ['-','+']) then begin
if ch='-' then sign:=true;
read(ch);
end;
while (ch in ['0'..'9']) do begin
root:=root*10+(ord(ch)-ord('0'));
read(ch);
end;
if sign then root:=root*-1;
while (ch<>'(') do read(ch);
read(ch);
a1:=find(root+top);
while (ch<>'(') do read(ch);
read(ch);
if not ans then a2:=find(root+top)
else a2:=true;

if (a1=a2) and (a1=false) and (root+top=num) then ans:=true;
if (not eoln) then read(ch);
find:=true;
end;
dec(deep);
end;

begin
while not eof do begin
read(num);
ans:=false;
read(ch);
while (ch=' ') do read(ch);
read(ch);
deep:=0;
find(0);
if ans then writeln('yes')
else writeln('no');
if ans and (not eoln) then readln;
end;
end.[/pascal]

hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

Test cases for 112 (Tree Summing)?

Post by hts »

I made a solution here, but I got WA for problem 112.
http://acm.uva.es/p/v1/112.html

Can anybody help me on this?

Code: Select all

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

FILE	*fin = stdin;
int	L, limite;
char	string[20000];
int	index;

int		aceitavel(char c)
{
	if(c == '(' || c == ')')
		return 1;
	else
	if(c <= '9' && c >= '0')
		return 1;
	else
		return 0;
}

int	recursao(int soma)
{
	int	atual;
	int	i1, i2;

	if(string[index] == '(' && string[index+1] == ')')
	{
		index += 2;
		return 0;
	}

	index++;

	/* valor do no atual */
	atual = atoi(&string[index]);

	/* soma dos antecessores */
	soma += atual;
	
	while(string[index] != '(')
		index++;

	/* esquerda */
	i1 = recursao(soma);
	if(i1 == -1)
		return -1;

	/* direita */
	i2 = recursao(soma);
	if(i2 == -1)
		return -1;
	
	if(!i1 && !i2)
		if(L == soma)
		{
			printf("yes\n");
			return -1; /* sai da recursao */
		}

	index++;
	return 1;
}

int	main()
{
	int	parenteses = 0, i;
	char	tmp;

/*	fin = fopen("treesum.txt", "r");	*/
	
	while(fscanf(fin, " %d", &L) == 1)
	{
		i = 0;

		while(fscanf(fin, "%c", &tmp) == 1 && aceitavel(tmp) == 0);

		/* copia a string da arvore descartando chars inuteis */
		do{
			if(tmp == '(')
				parenteses++;
			else
			if(tmp == ')')
				parenteses--;
			
			if(aceitavel(tmp) == 1)
				string[i++] = tmp;

			fscanf(fin, "%c", &tmp);
		}while(parenteses);

		string[i] = 0;

		index = 0;
		if(recursao(0) != -1)
			printf("no\n");
	}
}
Thank you very much.

Post Reply

Return to “Volume 1 (100-199)”