Page 3 of 10
[b]Help! Problem 112. Wrong Answer!!!!!!![/b]
Posted: Sun Jul 28, 2002 8:33 am
by Innovative Cat
[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]
112 SIGSEGV
Posted: Fri Aug 09, 2002 9:08 am
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
Annoying Runtime Error
Posted: Sat Aug 10, 2002 12:35 am
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.
112 -Tree Summing [runtime-error](SIGSEGV)
Posted: Fri Aug 23, 2002 5:12 am
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]
WA 112...
Posted: Wed Sep 04, 2002 7:57 pm
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();
}
}
112
Posted: Thu Oct 10, 2002 1:27 pm
by Master
[/b] How many leaf to root path is in the following tree
22 (5(10()(20))(10()()))
Posted: Thu Oct 10, 2002 2:44 pm
by Dominik Michniewski
I think that's incorrect input data ...
Maybe it should be
??
Dominik
Posted: Thu Oct 10, 2002 9:17 pm
by Moni
Is it a binary tree?
why you put those blank leaves after 20?
Posted: Fri Oct 11, 2002 8:07 am
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
if you find 112 is difficult............
Posted: Fri Nov 08, 2002 10:49 am
by luzi82
think of the negative input
Give me the test,please
Posted: Sun Dec 01, 2002 6:36 am
by nghiank
test
Posted: Wed Dec 04, 2002 8:28 am
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.
P 112: Why WA? :o
Posted: Thu Dec 12, 2002 8:31 am
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();
}
112 (Tree Summing) Recursion?
Posted: Thu Dec 19, 2002 6:39 pm
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]
Test cases for 112 (Tree Summing)?
Posted: Sat Feb 22, 2003 3:02 am
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.