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

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

Post by ImLazy » Sun Feb 06, 2005 6:20 pm

OK, now I get AC. The bug is the printf("\b\n");
I stay home. Don't call me out.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

122...I cant see my wrong

Post by lovemagic » Wed Dec 14, 2005 11:36 pm

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


khobaib

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Wed Jan 11, 2006 3:22 pm

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

User avatar
Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post by Jemerson » Tue Mar 21, 2006 1:39 am

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
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

122 wrong aswer

Post by beloni » Fri Apr 07, 2006 6:06 pm

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
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Fri Apr 07, 2006 9:06 pm

I'm sorry

I make a mistake....

please, dont care my previous post... :(

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Wed Feb 28, 2007 9:28 pm

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

owokko
New poster
Posts: 7
Joined: Sat Apr 28, 2007 7:11 am

Post by owokko » Tue May 08, 2007 11:26 am

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.
Last edited by owokko on Mon Aug 13, 2007 5:39 pm, edited 1 time in total.

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

122....RTE.....PLZZZ HELP

Post by SARKAR » Thu Jun 28, 2007 1:11 pm

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
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

Post by SARKAR » Thu Jun 28, 2007 1:15 pm


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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jun 28, 2007 1:24 pm

Search the board first. Don't open a new thread if one already exists.
Ami ekhono shopno dekhi...
HomePage

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Jun 28, 2007 2:04 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

Post by SARKAR » Thu Jun 28, 2007 2:33 pm

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
Last edited by SARKAR on Thu Jun 28, 2007 7:12 pm, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Jun 28, 2007 5:39 pm

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
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

Post by SARKAR » Thu Jun 28, 2007 7:11 pm

thnkss a lot i got a.c.

Post Reply

Return to “Volume 1 (100-199)”