Hi,
I submitted the following program for Problem 122. However I get WA. The program works for the sample input as well as other inputs I devised.
Please help.
------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;
void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;
node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;
int main()
{
/*build tree*/
/*First things first. Any non empty tree will require a root */
ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;
buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */
return 0;
}
void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;
while (1)
{
tempchar = getchar() ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */
tempchar = getchar() ;
if (tempchar == ')')
break ; /*last entry was read */
/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}
/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert the node in the tree */
insertnode(numstr, path) ;
}
}
void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;
/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value != NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}
void levelorder()
{
int i = 0 ;
int nextpos = 0 ;
/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;
i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}
int complete()
{
int i = 0;
while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}
void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;
i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
}
------------------------------------------------------------------------------
Thanks and Regards,
Ratnakar
122 - Trees on the level
Moderator: Board moderators
Re: WA to Problem 122,Trees on the Level". Please HELP
I assumed that the program would be tested one tree at a time. I will resubmit after putting in a loop.Rune Zedeler wrote:Over here the program does not work, and I cannot understand how you have tested it with success.
In your main routine you have no loops at all. How should the program be able to test more than one three - and hence correctly run the test example which have two trees?
Thanks. I had almost given up hope of getting a reply.
I tried putting in a lop, so that it reads all the input. It now works with the test input. However, now I get Time Limit exceeded. If I take out the loop and process each tree at a time, I get WA.
The code with the loop is given below:
--------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;
void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;
node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;
int main()
{
/*build tree*/
/*First things first. Any non empty tree will require a root */
while (1)
{
morethanonce = 0 ;
ptr_root = NULL ;
ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;
buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete\n") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */
}
return 0;
}
void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;
while (1)
{
if ((tempchar = getchar()) == EOF)
exit(0) ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */
tempchar = getchar() ;
if (tempchar == ')')
return ; /*last entry was read */
/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}
/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert
the node in the tree */
insertnode(numstr, path) ;
}
}
void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;
/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node
does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value == NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}
void levelorder()
{
int i = 0 ;
int nextpos = 0 ;
/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;
i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}
int complete()
{
int i = 0;
while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}
void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;
i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
printf("\n") ;
}
The code with the loop is given below:
--------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;
void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;
node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;
int main()
{
/*build tree*/
/*First things first. Any non empty tree will require a root */
while (1)
{
morethanonce = 0 ;
ptr_root = NULL ;
ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;
buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete\n") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */
}
return 0;
}
void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;
while (1)
{
if ((tempchar = getchar()) == EOF)
exit(0) ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */
tempchar = getchar() ;
if (tempchar == ')')
return ; /*last entry was read */
/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}
/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert
the node in the tree */
insertnode(numstr, path) ;
}
}
void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;
/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node
does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;
lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value == NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}
void levelorder()
{
int i = 0 ;
int nextpos = 0 ;
/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;
i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}
int complete()
{
int i = 0;
while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}
void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;
i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
printf("\n") ;
}
122 - WA
I've tried all of the different scenarios I could think of, and I don't think it's a logic problem or anything. Does anyone have any ideas for test data or see any things that might cause a problem?
[java]import java.util.*;
class Main{
static int[] tree = new int[256];
static int nodes = 0;
public static void main( String[] args ){
String g = "", tmp = "";
while( ( tmp = token() ) != null ){
g += tmp;
}
int x = 0;
while( ( x = g.indexOf("()") ) != -1 ){
String w = g.substring(0,x);
g = g.substring( x+2 );
neg();
createTree( w );
}
}
static void createTree( String w ){
StringTokenizer tok = new StringTokenizer(w, "(" );
while( tok.hasMoreTokens() ){
nodes++;
String element = tok.nextToken();
int x = Integer.parseInt( element.substring(0, element.indexOf(",") ) );
int loc = 0;
String bin = "1";
for( int i = element.indexOf(",") + 1 ; i < element.length()-1; i++ ){
if( element.charAt(i) == 'L' ) bin += 0;
else bin += 1;
}
loc = Integer.parseInt( bin, 2 );
loc--;
if( tree[loc] != -1 ){
System.out.println( "not complete" );
return;
}
tree[loc] = x;
}
boolean good = checkTree(0) == nodes;
if( ! good ) System.out.println( "not complete" );
else{
System.out.print( tree[0] );
for( int i = 1; i < tree.length; i++ )
if( tree != -1 ) System.out.print( " " + tree );
System.out.println();
}
}
static int checkTree( int x ){
if( x >= tree.length ) return 0;
if( tree[x] == -1 ) return 0;
return 1 + checkTree( x * 2 + 1 ) + checkTree( x * 2 + 2);
}
static void neg(){
for( int i = 0; i < tree.length; i++) tree = -1;
nodes = 0;
}
static String readLine(){return token( "\n" );}
static String token( ){return token( " \n\r\t" );}
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
}
[/java]
[java]import java.util.*;
class Main{
static int[] tree = new int[256];
static int nodes = 0;
public static void main( String[] args ){
String g = "", tmp = "";
while( ( tmp = token() ) != null ){
g += tmp;
}
int x = 0;
while( ( x = g.indexOf("()") ) != -1 ){
String w = g.substring(0,x);
g = g.substring( x+2 );
neg();
createTree( w );
}
}
static void createTree( String w ){
StringTokenizer tok = new StringTokenizer(w, "(" );
while( tok.hasMoreTokens() ){
nodes++;
String element = tok.nextToken();
int x = Integer.parseInt( element.substring(0, element.indexOf(",") ) );
int loc = 0;
String bin = "1";
for( int i = element.indexOf(",") + 1 ; i < element.length()-1; i++ ){
if( element.charAt(i) == 'L' ) bin += 0;
else bin += 1;
}
loc = Integer.parseInt( bin, 2 );
loc--;
if( tree[loc] != -1 ){
System.out.println( "not complete" );
return;
}
tree[loc] = x;
}
boolean good = checkTree(0) == nodes;
if( ! good ) System.out.println( "not complete" );
else{
System.out.print( tree[0] );
for( int i = 1; i < tree.length; i++ )
if( tree != -1 ) System.out.print( " " + tree );
System.out.println();
}
}
static int checkTree( int x ){
if( x >= tree.length ) return 0;
if( tree[x] == -1 ) return 0;
return 1 + checkTree( x * 2 + 1 ) + checkTree( x * 2 + 2);
}
static void neg(){
for( int i = 0; i < tree.length; i++) tree = -1;
nodes = 0;
}
static String readLine(){return token( "\n" );}
static String token( ){return token( " \n\r\t" );}
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
}
[/java]
Last edited by Spike on Mon Dec 16, 2002 6:44 am, edited 1 time in total.
HELP
here is my code for 122. I got WA, too.
can anyone give me some test cases or help me with my code???
[cpp]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);
for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(')
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')')
{
temp=c;
if(c<58 && c>47)
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')')
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else
{
ch=0;
for(i=count;i>0;i--)
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}
void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;
for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}
if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}
}
[/cpp]
can anyone give me some test cases or help me with my code???
[cpp]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);
for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(')
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')')
{
temp=c;
if(c<58 && c>47)
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')')
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else
{
ch=0;
for(i=count;i>0;i--)
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}
void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;
for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}
if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}
}
[/cpp]
here's a hint
i tried 122 too, and got WA.
i was sure my program was correct, even thought the judge might be corrupted
then i read the problem again and realize i missed something BIG:
If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed.
it took only a few seconds to fix the problem...
i was sure my program was correct, even thought the judge might be corrupted
then i read the problem again and realize i missed something BIG:
If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed.
it took only a few seconds to fix the problem...
??
but.....epsilon0,
if I don't misunderstand, I don't think my code would neglect what you metioned.
Can you give me some test cases?
or can you try my code and tell me what's wrong?
thx a lot~
if I don't misunderstand, I don't think my code would neglect what you metioned.
Can you give me some test cases?
or can you try my code and tell me what's wrong?
thx a lot~
here is your error
running your program:
> (0,L) ()
< 0
>
clearly your program should output "not complete\n", not "0\n". a tree needs a root, right?
i can't see where the error lies within your program because it's unreadable
> (0,L) ()
< 0
>
clearly your program should output "not complete\n", not "0\n". a tree needs a root, right?
i can't see where the error lies within your program because it's unreadable
....
I fix the bug....but still got WA....><
I also find something strange...
can two nodes have the same value??
ex: (5,) (4,L) (4,R) ()
my code will print 5 4 4
thx for help~~
I also find something strange...
can two nodes have the same value??
ex: (5,) (4,L) (4,R) ()
my code will print 5 4 4
thx for help~~
-
Dominik Michniewski
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
yes, two (or more) nodes can have the same value .... 
why not ?
If you want to get accepted in this problem, assume that you must have a proper tree after reading all nodes belongs to it. that means:
1) any node within the tree must be defined (must have a value in input)
2) any node can't be defined twice ...
Algorithm is quite simple - read data and build tree)
It's all - if this in not enough - you must have a bug inside your code .
I have a problem with this quesion long time ago - I got RTE first time. But I discovered, that I can't free memory in C. When I commented line which fries memory I got Acepted
Best regards
Dominik
why not ?If you want to get accepted in this problem, assume that you must have a proper tree after reading all nodes belongs to it. that means:
1) any node within the tree must be defined (must have a value in input)
2) any node can't be defined twice ...
Algorithm is quite simple - read data and build tree
)It's all - if this in not enough - you must have a bug inside your code .
I have a problem with this quesion long time ago - I got RTE first time. But I discovered, that I can't free memory in C. When I commented line which fries memory I got Acepted
Best regards
Dominik
hmm...dominik
here's my code now
I think it will do what you said, but I got another WA.....
why~~
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);
for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(') /*start to catch a node*/
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')') /*while it's not a node's end*/
{
temp=c;
if(c<='9' && c>='0')
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')') /*if it's the end of a tree*/
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else /*if it's not the end of a tree*/
{
ch=0;
for(i=count;i>0;i--)
/*the following are insertion sort to sort the nodes */
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}
/*the function is to check if the input is a valid tree*/
void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;
for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(n[0]==0) esc=1;
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}
if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}
}
[/c]
here's my code now
I think it will do what you said, but I got another WA.....
why~~
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);
for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(') /*start to catch a node*/
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')') /*while it's not a node's end*/
{
temp=c;
if(c<='9' && c>='0')
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')') /*if it's the end of a tree*/
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else /*if it's not the end of a tree*/
{
ch=0;
for(i=count;i>0;i--)
/*the following are insertion sort to sort the nodes */
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}
/*the function is to check if the input is a valid tree*/
void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;
for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(n[0]==0) esc=1;
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}
if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}
}
[/c]
Last edited by cym on Sat Nov 23, 2002 2:33 pm, edited 1 time in total.
-
Dominik Michniewski
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
BTW Why don't you use character names instead of numbers ?
More readable is than
I try to check your program afternoon ..... I'm working now and I don't have a C++ compiler to run your code ...
Best regards
Dominik
?More readable is
Code: Select all
if((ch >'0') %% (ch < '9')) Code: Select all
if((ch > 49) %% (ch < 58)) Best regards
Dominik
-
Dominik Michniewski
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
sorry~~
I can't use private message....
can you give me your email??
my email is atias@pchome.com.tw
thx~~
I can't use private message....
can you give me your email??
my email is atias@pchome.com.tw
thx~~