122 - Trees on the level

[ImLazy]

OK, now I get AC. The bug is the printf("\b\n");

[lovemagic]

I got several wa in this problem.Can smbody fix my bug?

Code: Select all

#include <stdio.h>
#include <math.h>
#include <string.h>
#define max 500
int m[max][max];
int f=1,n;
char nn[15],s[30],inp[30];
int row,col,hr,hc;

void process(){
    int i,j,k;
    if(f==0){
        printf("not complete\n");
        return;
    }    
    for(i=hr;i>0 && f;i--){          //check if parents exist
        hc=1<<i;
        for(j=hc-1;j>=0 && f;j--)
            if(m[i][j]>0 && m[i-1][j/2]==0)f=0;  
    } 
    if(f==0){
        printf("not complete\n");
        return;
    }    
    for(i=0;i<=hr;i++){             // print the value which is>0
        k=1<<i;
        for(j=0;j<=k;j++)
            if(m[i][j]!=0)printf(" %d",m[i][j]);
    }    
    printf("\n");
    return;    
}    

void init(){
    int i,j,k;
    for(i=0;i<=hr;i++){
        k=1<<i;
        for(j=0;j<=k;j++)
            m[i][j]=0;
    }    
}    

int main(){
    int i,j,k;
    while(scanf("%s",inp)!=EOF){
        if(strcmp(inp,"()")==0){
            process();
            init();
            hr=0;
            f=1;
        }    
        else{
            if(f==0)continue;
            for(i=1,j=0;inp[i]!=',';i++)           // get the value of node from input
                nn[j++]=inp[i];
            nn[j]=NULL;

            sscanf(nn,"%d",&n);  
            i++;
            for(i,j=0;inp[i]!=')';i++)            // get the position from input
                s[j++]=inp[i];
            s[j]=NULL;
            row=strlen(s);                        
            if(row>hr)hr=row;
            col=0;
            for(i=0;s[i];i++){                       //build table
                if(s[i]=='L')col*=2;
                else if(s[i]=='R')col=col*2+1;
            }    
            if(m[row][col]==0)                  //finding diferent node in same position
                m[row][col]=n;
            else f=0;                            // if 2 node found in same position flag=0
        }    
    }    
    return 0;
}    

[beloni]

I'm trying to solve this problem too...
but I think that your code is a bit of confuse...

what means the var f ???

if you write better your code maybe I can help you...

[Jemerson]

In order to test what the guys said, try the following input:

Code: Select all

(1,) 
(2,L) 
(3,LL) 
(4,LLL) 
(5,LLLL) 
(6,LLLLL) 
(7,LLLLLL) 
(8,LLLLLLL) 
(9,LLLLLLLL) 
(10,LLLLLLLLL) 
(11,LLLLLLLLLL) 
(12,LLLLLLLLLLL) 
(13,LLLLLLLLLLLL) 
(14,LLLLLLLLLLLLL) 
(15,LLLLLLLLLLLLLL) 
(16,LLLLLLLLLLLLLLL) 
(17,LLLLLLLLLLLLLLLL) 
(18,LLLLLLLLLLLLLLLLL) 
(19,LLLLLLLLLLLLLLLLLL) 
(20,LLLLLLLLLLLLLLLLLLL) 
(21,LLLLLLLLLLLLLLLLLLLL)
()

The output is:

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Good Luck

[beloni]

hello

Trying to solve this problem, I've got some WA:
[/code]
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstring>

#define MAX 1000000

using namespace std;


class Heap
{
private:
int node[MAX];
int last;

public:
Heap();

void reset();
int getleft( int pos ) const;
int getright( int pos ) const;
int getprev( int pos ) const;
bool insert( const char *new_node );
bool vprint() const;
};


Heap::Heap()
{
for( int w = 0; w < MAX; w++ )
node[w] = -1;
last = -1;
}


void Heap::reset()
{
for( int w = 0; w <= last; w++ )
node[w] = -1;
last = -1;
}


int Heap::getleft( int pos ) const { return ( 2 * pos + 1 ); }

int Heap::getright( int pos ) const { return ( 2 * pos + 2 ); }

int Heap::getprev( int pos ) const
{
if( pos % 2 ) return ( pos / 2 );
else return ( pos / 2 -1 );
}


bool Heap::insert( const char *new_node )
{
istringstream sinput( new_node );
char strv[MAX], pos[MAX];

sinput.ignore(); // ignores '('
sinput.getline( strv, MAX-1, ',' );
sinput.getline( pos, MAX-1, ')' );

int new_value = atoi( strv );
int target = 0; // root position

// calculating the values position
for( int w = 0; pos[w] != 0; w++ )
if( pos[w] == 'L' )
target = getleft( target );
else
target = getright( target );

if( node[target] < 0 )
{
node[target] = new_value;
if( target > last ) last = target;

return true;
}
else
return false; // more than once
}



bool Heap::vprint() const
{
// verifing if a node is not given a value
for( int w = 1; w <= last; w++ )
if( node[w] >= 0 ) // if exists a node
if( node[getprev(w)] < 0 ) // with no previous
return false; // it is not complete

for( int w = 0; w <= last; w++ )
if( node[w] >= 0 )
cout << node[w] << " ";
cout << endl;

return true;
}



int main()
{
char input[MAX];
Heap my_heap;

while( cin >> input )
{
if( strcmp( input, "()" ) != 0 )
{
if( !my_heap.insert( input ) )
{
cout << "not complete" << endl;
// continue reading
while( cin >> input )
if( strcmp( input, "()" ) == 0 ) break;
}
}
else
{
if( !my_heap.vprint() )
cout << "not complete" << endl;

my_heap.reset();
}
}

return 0;
}

Code: Select all

so, I think the problem is in input:

while( cin >> input )
{
if( strcmp( input, "()" ) != 0 )
{
if( !my_heap.insert( input ) )
{
cout << "not complete" << endl;
// continue reading
while( cin >> input )
if( strcmp( input, "()" ) == 0 ) break;
}
}
else
{
if( !my_heap.vprint() )
cout << "not complete" << endl;

my_heap.reset();
}
}

Code: Select all

can anyone help me ???
thanks

[beloni]

I'm sorry

I make a mistake....

please, dont care my previous post...

[mukeshtiwari]

thnkx for ur inputs ..ur inputs are really helped me lot to solve this problems ...

[owokko]

I get WA for this problem. Can anyone get me some test case?

The step I solve problem is:

1. buliding Tree (node with node_pointer L, R and int D)

2. when I add a value to Tree, I will chaeck out the target node has been assign a value or not. (if the node has been assign a value. isComplete =0)

3. trace Tree, if there is a node has been never assign a value, isComplete =0

4. if isComplete =0 output "not complete" else ouput the result of Level order traversal

PS1. The Level order traversal is implementation by Queue.
PS2. The Queue is implementation by Array


Is OJ input will input empty tree "()"?? if it is, I output "not complete".

I have test so many case but still get WA. plz help me.

[SARKAR]

my program give following run time error whn submitted
plzzz help i m in gr8 fix

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h: In method `pair<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,char[2]>::pair(const string &, const char (&)[2])':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h:68: instantiated from `make_pair<string, char[2]>(const string &, const char (&)[2])'
05700544_24.c:64: instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h:44: incompatible types in assignment of `const char[2]' to `char[2]'

here is my code

Code: Select all

#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
struct tree
{
map<string,string> member;
};
map<string,string>::iterator pos,pos1;
string s;
int max=0,count=0;
tree level[20];
while(cin>>s)
{
string str1,str2;
if(s!="()")
{
int i=1;
while(s[i]!=',')
{
str1.push_back(s[i]);
++i;
}
++i;
while(s[i]!=')')
{
str2.push_back(s[i]);
++i;
}
if(max<str2.length())
max=str2.length();
level[str2.length()].member.insert(make_pair(str2,str1));
count++;
}
else
{
int count1=0;
for(int i=0;i<=max;++i)
{
count1=count1+level[i].member.size();
if(level[i].member.size()==0)
{
count1=-1;
break;
}
}
int i,mark=0;
if(count1!=count)
printf("not complete\n");
else
{
for(i=max;i>=2;--i)
for(pos=level[i].member.begin();pos!=level[i].member.end();++pos)
{
string test;
int y=pos->first.length()-1;
for(int k=0;k<y;++k)
test.push_back(pos->first[k]);int o=level[i-1].member.size();
level[i-1].member.insert(make_pair(test," "));
if(level[i-1].member.size()>o)
{
mark=101;
break;
}
}
if(mark==101)
printf("not complete");
else
for(i=0;i<=max;++i)
{
for(pos=level[i].member.begin();pos!=level[i].member.end();++pos)
cout<<pos->second<<"  ";
level[i].member.clear();
}
cout<<"\n";
}
count=0,max=0;
}
}
}

[SARKAR]

i think thr is some problem in make_pair but i always use it like this only.........
it is working fine on my pc......

[Jan]

Search the board first. Don't open a new thread if one already exists.

[little joey]

You've been told before: don't open a new thread, if one already exists for your problem. I've deleted your message and locked the thread.

[SARKAR]

my program give following compile error whn submitted
plzzz help i m in gr8 fix

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h: In method `pair<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,char[2]>::pair(const string &, const char (&)[2])':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h:68: instantiated from `make_pair<string, char[2]>(const string &, const char (&)[2])'
05700544_24.c:64: instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/stl_pair.h:44: incompatible types in assignment of `const char[2]' to `char[2]'

here is my code

Code: Select all

removed after a.c

[chunyi81]

Check this line:

Code: Select all

level[i-1].member.insert(make_pair(test," ")); 

It's the only place which has a 2-character string array. You are assigning a " " (taken to be a const string) to a non-const string. Try something like the following:

Code: Select all

string space(" ");
level[i-1].member.insert(make_pair(test,space)); 

[SARKAR]

thnkss a lot i got a.c.