122 - Trees on the level

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

Dows
New poster
Posts: 3
Joined: Mon Apr 19, 2004 12:19 am

Post by Dows » Tue Apr 20, 2004 5:46 pm

still desperated... :(

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

122- Trees on the level : Runtime Error(SIGSEGV)

Post by pipo » Wed May 12, 2004 12:46 am

Can you tell me what's wrong with my code ?
i've tried to submit several times, but i've got a message 'Runtime Error(SIGSEGB)'
I would like to know why I got the message..
and ... what case the message is shown?

[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct _node {
unsigned int data;
int level;
char loc[256];
};

_node node[256];
int nodeCount = 0;

int in();
bool isOK();
void print();
void init();

void main(void)
{
int key;
init();

while ( 1 ) {
key = in();

if ( key == -1 ) break;

if ( key == 0 ) {
if ( isOK() == 0 )
printf("not complete\n");
else {
print();
printf("\n");
}

init();
nodeCount = 0;

};

if ( key == 1 ) {
printf("not complete\n");
init();
nodeCount = 0;
};

};


}

void init()
{
int i;

for ( i = 0 ; i < nodeCount ; i++ ) {
node.data = 0;
node.level = -1;
strcpy(node.loc, "");
}

}

int in()
{
char temp[300];
char value[10] = "";
char pos[256] = "";

int i, j;
int l;

int insLoc;


if ( scanf("%s", temp) == 0 ) return -1;

if ( strcmp(temp, "()") == 0 ) return 0;

j = 0;


for ( i = 1 ; temp != ',' ; i++ )
value[j++] = temp;
value[j] = '\0';


if ( strcmp(value, "") == 0 ) {

while ( 1 ) {
scanf("%s", temp);

if ( strcmp(temp, "()") == 0 ) return 1;
};
};



i++;



for ( l = 1 ; temp != ')' ; i++, l++)
pos[l-1] = temp;
pos[l-1] = '\0';



for ( i = 0 ; i < nodeCount ; i++ ) {
if ( node.level > l ) break;

if ( node.level == l && strcmp(node.loc, pos ) > 0 ) break;

if ( node[i].level == l && strcmp(node[i].loc, pos) == 0 ) {

while ( 1 ) {
scanf("%s", temp);
if ( strcmp(temp, "()") == 0 ) return 1;
};
}
}



insLoc = i;

for ( i = nodeCount ; i > insLoc ; i-- ) {
node[i].data = node[i-1].data;
node[i].level = node[i-1].level;
strcpy(node[i].loc, node[i-1].loc);
}

node[insLoc].level = l;
node[insLoc].data = atoi(value);
strcpy(node[insLoc].loc, pos);

nodeCount++;

return 2;
}

bool isOK()
{
int i, j;

int parlevel;
char parStr[256] = "";


if ( node[0].level != 1 ) return 0;


for ( i = 1 ; i < nodeCount ; i++ ) {
parlevel = node[i].level - 1;

if ( parlevel == 1 ) continue;

strcpy(parStr, "");

strcpy(parStr, node[i].loc);
parStr[strlen(parStr)-1] = '\0';


for ( j = 1 ; node[j].level < parlevel ; j++ );


while ( 1 ) {
if ( node[j].level != parlevel ) return 0;

if ( strcmp(parStr, node[j].loc) == 0 ) break;

j++;
};

}

return 1;
}

void print()
{
int i;

for ( i = 0 ; i < nodeCount; i++ )
printf("%d ", node[i].data);
}
[/cpp]

Thanks./.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed May 12, 2004 2:18 am

[cpp]for ( i = nodeCount ; i > insLoc ; i-- ) { [/cpp]

This line looks mighty suspicious!

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

well....

Post by pipo » Wed May 12, 2004 3:17 am

well..... I don't think so...

the line is right exactly...

In my thinking it's line for insertion sorting....

i don't doubt the line.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

well...

Post by pipo » Wed May 12, 2004 4:07 am

hi...

in my opinion, in following case....

(,L) (1,) ()
-> "not complete".. the first node's value doesn't exist...

(,L) (2,L) (1,) ()
-> "not complete".. it's same reason ...

if you didnt get accepted from the judge, you probably dont think this case.. are you ????? [/cpp]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed May 12, 2004 4:32 am

You're right.. I was just skimming it and thought it looked like a fishy array out of bounds error..

On further inspection, you handle reading end of file incorrectly.

You should probably use something like
[cpp]if (scanf ("%s", temp) != 1) return -1;[/cpp]

It's typically safer, since then you stop whenever you don't read that 1 thing you want to read.

BTW, scanf returns EOF (which is -1) when it reaches end of file, so it continues to run since you're only checking against 0, which is what your program is doing, and thus, it tries to access some junk later somewhere, and it crashes.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

oh~

Post by pipo » Wed May 12, 2004 4:54 am

thanks a lot...

due to you, i have got accepted....

because of this problem... i had taken about 3 days....

but.... hm....

why i got accepted(P.E) ???

what is difference Accepted and Accepted(P.E)... ???

please explain to me using examples....

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed May 12, 2004 2:27 pm

Accepted means your output exactly matches that of the judge. Accepted (P.E.) means the data is correct, but the presentation is off, meaning you have some additional spaces or newlines somewhere (or lack thereof), but the actual data is correct.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » Wed May 12, 2004 3:21 pm

ah... i see....

thanks a lot...

Eug
New poster
Posts: 2
Joined: Thu Jul 15, 2004 7:33 pm
Location: Kazakhstan

Why WA with 122???

Post by Eug » Fri Jul 16, 2004 4:15 pm

I can't understand why I got WA on submitting this problem. Please, if got some free time look at this source. Or if someone has tests could you send them. Thanks a lot. :)


program p122(input,output);

{$APPTYPE CONSOLE}
const nn=16384;
type
node = record
n,
s:string;
end;

var
tree: array[1..nn] of node;
count,a:integer;
{****************************************************************************}
procedure readInput;
var
ch:char;
ex,comma:boolean;
begin
count:=1;
ex:=false;
comma:=false;
while (true) do begin
read(ch);
if ch=',' then comma:=true;
if (ch<>'(') and (ch<>',') and
(ch<>')') and (ch<>' ') and
(ch<>chr(13)) and (ch<>chr(10))then
if (not comma) then
tree[count].n:=tree[count].n+ch
else
tree[count].s:=tree[count].s+ch;
{} if (ch=' ')or(ch=chr(13)) then begin
count:=count+1;
comma:=false;
end;
{} if (ch=')') and ex then break
else ex:=false;
if ch='(' then ex:=true;
end;{ ch = '()', exit from the LOOP }

count:=count-1;

{ for ii:=1 to count do begin
writeln(tree[ii].n, ' -> ' ,tree[ii].s,'!', length(tree[ii].s));
end;}
end;

{*****************************************************************************}
procedure sort;
var key: node;
ready: array [1..nn] of node;
sorted:array [1..(nn div 2)] of node;
i,ii,j,k,readyfilled:integer;
begin
{here we choose strings with length 1,2,3,...,
each sort alphbetically and then add it to temporary string
called ready }

readyFilled:=1;
for ii:=0 to 1000 do begin
{here we choose strings with length 1,2,3,...}
k:=0;
for j:=1 to count do begin
{write(length(tree[j].s),' ');}
if length(tree[j].s) = ii then begin
k:=k+1;
sorted[k]:=tree[j];
end;
end;

{here we sort the array sorted}
for j:=2 to k do begin
key:=sorted[j];
i:=j-1;
while (i>0) and (sorted.s>key.s) do begin
sorted[i+1]:=sorted;
i:=i-1;
end;
sorted[i+1]:=key;
end;

{then we put sorted elements from sorted[] in ready}
j:=1;
for i:=readyFilled to readyFilled+k do begin
ready:=sorted[j];
j:=j+1;
end;
readyFilled:=readyFilled+k;
end;
{writeln;writeln;writeln('result:');}
for ii:=1 to count do begin
{ writeln(ready[ii].n, ' -> ' ,ready[ii].s,'!');}
tree[ii]:=ready[ii];
end;
end;


{*****************************************************************************}
function complete:boolean;{ checks wether this tree is complete}
{this function checks whether tree[] is complete or not complete}
var
i,j,ds,dn,down:integer;
isIn1,isIn2,isIn3:boolean;
key:string;
begin
isIn1:=false;isIn2:=false;isIn3:=false;
{first check is on a root existance}
if length(tree[1].s)<>0 then isIn1:=true;

{Second check looks up for repeated elements}
j:=0;ds:=0;dN:=0;
while (not isIn2)and(j<=count) do begin
j:=j+1;
for i:=1 to count do begin
if tree[j].s=tree.s then ds:=ds+1;
if tree[j].n=tree.n then dN:=dN+1;
end;
if ds>1 then isIn2:=true;
//if dN>1 then isIn2:=TRUE;
ds:=0;
//dN:=0;
end;{ element within twise or j>count }


{Third check is on }
ds:=0;down:=4;
if (length(tree[3].s)<>1) then down:=down-1;
if (length(tree[2].s)<>1) then down:=down-1;
for i:=count downto down do begin
key:= tree.s;
key:=copy(key,1,length(key)-1);
for j:=1 to count do begin
if (key=tree[j].s)and(length(key)=length(tree[j].s)) then
begin
ds:=ds+1;
end;
end;
{ writeln(dd,' key-',key);}
if ds=0 then isIn3:=true
else ds:=0;
end;
{writeln('All checks are passed');}
if isIn3 or isIn2 or isIn1 then complete:=false
else complete:=true;
end;

procedure print;
var i:integer;
begin
for i:=1 to count do
write(tree.n,' ');
end;
BEGIN
assign(input,'p122.in');reset(input);
assign(output,'p122.out');rewrite(output);

while not eof(input) do begin
readInput;
sort;
if complete then
print
else
write('not complete');
for a:=1 to count do begin
tree[a].n:='';
tree[a].s:='';
end;
readln;
writeln;
end;
close(input);close(output);
END.
All is the Vanity

Vegeta
New poster
Posts: 3
Joined: Wed Sep 11, 2002 7:20 pm
Contact:

Post by Vegeta » Sun Jul 25, 2004 6:13 am

rcotta wrote:I found what I was doing wrong. When I read the tree could have at most 256 nodes, I assumed its depth would be at most 8, but it is not true.

Fixed this and know my code works.
You saved me, Cotta, thanks!

-- Martinelli.

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

122 stil WA

Post by Bug! » Tue Aug 10, 2004 3:33 am

Hi everybody...
I try to solve this problem using 2 different way... And both of all get WA..
I don't know why.. Can anybody give me some input...
Here's my 1st code (using tree):
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 300

char valid;
double isi[MAX][MAX];
long top[MAX];

struct tree{
double num;
struct tree*L,*R;
}*root;

void push(struct tree**curr, char in[],double num){
if(!(*curr)){
(*curr)=(struct tree*)malloc(sizeof(struct tree));
(*curr)->L=(*curr)->R=0;
(*curr)->num=-1;
}
if(in[0]=='L')
push(&(*curr)->L,in+1,num);
else if(in[0]=='R')
push(&(*curr)->R,in+1,num);
else{
if((*curr)->num!=-1)valid=0;
(*curr)->num=num;
}
}

void pop(struct tree *curr,long level){
isi[level][top[level]]=curr->num;
top[level]++;
if(curr->L)pop(curr->L,level+1);
if(curr->R)pop(curr->R,level+1);
if(curr->num==-1)valid=0;
free(curr);
}

int main(){
char temp[1001],query[301],OK;
double num;
long i,j;

#ifndef ONLINE_JUDGE
freopen("122.in","r",stdin);
freopen("122.out","w",stdout);
#endif

while(scanf("%s",temp)==1){
if(strcmp(temp,"()")){
root=0;
sscanf(temp,"(%lf,%[^)]",&num,&query);
push(&root,query,num);
valid=1;
while(1){
scanf("%s",temp);
if(strcmp(temp,"()")==0)
break;
sscanf(temp,"(%lf,%[^)]",&num,&query);
push(&root,query,num);
}
for(j=0;j<MAX;j++)
top[j]=0;
for(j=0;j<MAX;j++)
for(i=0;i<MAX;i++)
isi[j]=-1;
pop(root,0);
OK=0;
if(valid){
for(j=0;j<MAX;j++){
for(i=0;i<MAX;i++){
if(isi[j]==-1)break;
else {
if(OK)printf(" "); OK=1;
printf("%.0lf",isi[j]);
}
}
}
}
else
printf("not complete");
printf("\n");
}
else
printf("not complete\n");
}
return 0;
}[/c]
and this is my 2nd code (just use array and sort it)
[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int now;

struct input{
double num;
char query[301];
}data[300];

void input(double num,char query[]){
strcpy(data[now].query,query);
data[now].num = num;
query[0]=0;
}

void sort(void){
struct input temp;
int i,j,x,y;
for(i=0;i<now;i++){
for(j=i+1;j<now;j++){
x = strlen(data.query);
y = strlen(data[j].query);
if((y<x)||(x==y&&strcmp(data.query,data[j].query)>0)){
temp = data;
data = data[j];
data[j] = temp;
}
}
}
}

int main(){
char temp[1001],query[301],OK;
long i,j;
double num;

#ifndef ONLINE_JUDGE
freopen("e:\\122.in","r",stdin);
freopen("e:\\122.out","w",stdout);
#endif

while(scanf("%s",temp)==1){
now = 0;
if(strcmp(temp,"()")){
sscanf(temp,"(%lf,%[^)]",&num,&query);
input(num,query);
now++;
while(1){
scanf("%s",temp);
if(strcmp(temp,"()")==0)
break;
sscanf(temp,"(%lf,%[^)]",&num,&query);
input(num,query);
now++;
}
sort();
OK=1;
for(i=1; i<now; i++){
if(strcmp(data.query,data[i-1].query)==0){
OK=0;
break;
}
}
if(OK){
for(i=now-1;i>0;i--){
strcpy(temp,data.query);
temp[strlen(data.query)-1]=0;
for(j=0;j<i;j++){
if(strcmp(data[j].query,temp)==0)
break;
else if(j==i-1){
OK=0;
break;
}
}
}
if(OK){
for(i=0;i<now;i++)
printf("%.0lf ",data[i].num);
printf("\n");
}
}
if(!OK){
printf("not complete\n");
}
}
}
return 0;
}
[/c]
Thx before...
Regard,
Andre

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

#122, still WA, I'm getting crazy.

Post by ImLazy » Sun Jan 30, 2005 6:30 pm

Code: Select all

input:
()
(,) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(22,) (33,L) (44,LL) ()
(22,) (44,LL) ()
(11,LL) (7,LLL) (8,R) ()
(11,LL) (7,LLL) (8,R) (6,L) (4,) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) (2,RRR) ()
(5,) (4,L) (13,RL) (5,L) (6,R) ()
(5,) (6,L) ()
(3,) ()
(4,LL) (3,L) (2,) (6,R) ()
(,L) (22,L) (22,) ()
(3,R) (,L) (22,L) (22,) ()

my output:

Code: Select all

not complete
not complete
5 4 8 11 13 4 7 2 1
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
2 3 6 4
not complete
not complete

Help!!!!!
This is my code:

Code: Select all

#include<stdio.h>
#include<string.h>
int main()
{
  struct node
  {
    long value;
    int visit;
    struct node *father,*left,*right;
  };
  struct node V[256],
              *p;
  int cnt_node,
      max_level,temp_level,
      not,
      i,j;
  long n;
  char c,specify[300];
  while(1)  
  {
    for(i=0;i<256;i++)
    {
      V[i].value=0;
      V[i].father=NULL;
      V[i].left=NULL;
      V[i].right=NULL;
    }
    max_level=0;
    cnt_node=1;
    not=0;
    while(1)
    {
      if(scanf("%s",specify)!=1)
        return 0;
      if(strlen(specify)==2)
        break;
      n=0;
      i=1;
      c=specify[i];
      while(c<='9' && c>='0')
      {
        n*=10;
        n+=c-'0';
        i++;
        c=specify[i];
      }
      if(n==0)
        not=1;
      p=&V[0];
      temp_level=0;
      while(c!=')')
      {
        if(c=='L')
        {
          if(p->left==NULL)
          {
            p->left=&V[cnt_node];
            cnt_node++;
          }
          p->left->father=p;
          p=p->left;
          temp_level++;
        }
        else if(c=='R')
        {
          if(p->right==NULL)
          {
            p->right=&V[cnt_node];
            cnt_node++;
          }
          p->right->father=p;
          p=p->right;
          temp_level++;
        }
        i++;
        c=specify[i];
      }
      if(temp_level>max_level)
        max_level=temp_level;
      if(p->value==0)
        p->value=n;
      else
        not=1;
    }
    if(not==1)
      printf("not complete\n");
    else
    {
      not=0;
      for(i=0;i<cnt_node;i++)
        V[i].visit=0;
      p=&V[0];
      while(V[0].visit!=2)
      {
        if(p->value==0)
        {
          not=1;
          break;
        }
        if(p->visit==0)
          if(p->left==NULL)
            p->visit++;
          else
            p=p->left;
        else if(p->visit==1)
          if(p->right==NULL)
            p->visit++;
          else
            p=p->right;
        else
        {
          p=p->father;
          p->visit++;
        }
      }
      if(not==1)
        printf("not complete\n");
      else
      {
        printf("%ld ",V[0].value);
        for(i=1;i<=max_level;i++)
        {
          for(j=0;j<cnt_node;j++)
            V[j].visit=0;
          p=&V[0];
          temp_level=0;
          while(V[0].visit!=2)
          {
            if(temp_level==i)
            {
              printf("%ld ",p->value);
              p=p->father;
              p->visit++;
              temp_level--;
            }
            else if(p->visit==0)
              if(p->left==NULL)
                p->visit++;
              else
              {
                p=p->left;
                temp_level++;
              }
            else if(p->visit==1)
              if(p->right==NULL)
                p->visit++;
              else
              {
                p=p->right;
                temp_level++;
              }
            else
            {
              p=p->father;
              p->visit++;
              temp_level--;
            }
          }
        }
        printf("\b\n");
      }
    }
  }
}
Last edited by ImLazy on Sun Feb 06, 2005 6:22 pm, edited 4 times in total.
I stay home. Don't call me out.

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

Post by ImLazy » Mon Jan 31, 2005 2:52 pm

Any one helps me!? If you get AC, then can you tell me whether your program has the same output as mine?
I stay home. Don't call me out.

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

Post by ImLazy » Mon Jan 31, 2005 4:06 pm

I think the input like (,L) or (,) doesn't exist, because the problem says:"All nodes contain a positive integer".
I stay home. Don't call me out.

Post Reply

Return to “Volume 1 (100-199)”