122 - Trees on the level

[Dows]

still desperated...

[pipo]

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./.

[UFP2161]

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

This line looks mighty suspicious!

[pipo]

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]

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]

[UFP2161]

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]

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

[UFP2161]

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]

ah... i see....

thanks a lot...

[Eug]

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.

[Vegeta]

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!]

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

[ImLazy]

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");
      }
    }
  }
}

[ImLazy]

Any one helps me!? If you get AC, then can you tell me whether your program has the same output as mine?

[ImLazy]

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