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

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Mon Dec 03, 2007 7:45 pm

I got WA.

Here is my code:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node
{
	int value;
	char path[300];
}n[300];



int cmp(const void *a,const void *b)
{
	char c[300],d[300];
	int e,f;
	strcpy(c,((node*)a)->path);
	strcpy(d,((node*)b)->path);
	e = ((node*)a)->value;
	f = ((node*)b)->value;
	if(strlen(c)>strlen(d))
		return 1;
	else if(strlen(c)==strlen(d))
	{
		return strcmp(c,d);
	}
	else
		return -1;
}


int main()
{
	char in[300],temp[300],used[1000000];
	
	int index = 0,i,j,len,flag = 0,pos;
	//freopen("122.in","r",stdin);
	while(scanf("%s",in)!=EOF)
	{
		if(in[1]==')')
		{
			if(index==0)
			{
				printf("not complete\n");
				continue;
			}
			for(i = 0;i<100000;i++)
				used[i] = 0;
			qsort(n,index,sizeof(n[0]),cmp);
			for(i = 0;i<index;i++)
			{
				pos = 1;
				for(j = 0;n[i].path[j];j++)
				{
					if(n[i].path[j]=='L')
						pos*=2;
					else
						pos = 2*pos + 1;
				}
				if(pos==1)
					used[pos] = 1;
				else
				{
					if(used[pos/2]!=1)
						flag=1;
					else if(used[pos])
						flag=1;
					used[pos] = 1;
				}

			}
			if(flag)
				printf("not complete\n");
			else
			{
				printf("%d",n[0].value);
				for(i = 1;i<index;i++)
					printf(" %d",n[i].value);
				printf("\n");
			}
			flag = 0;
			index = 0;
		}
		else
		{
			len = strlen(in);
			for(i = 1;i<len-1;i++)
			{
				if(in[i]==',')
					break;
				temp[i-1] = in[i];
			}
			temp[i-1] = '\0';
			if(i==1)
				flag = 1;
			else
				n[index].value = atol(temp);
			for(i++,j = 0;i<len-1;i++,j++)
				n[index].path[j] = in[i];
			n[index].path[j] = '\0';
			index++;

		}
	}
	return 0;
}


Plz help...

Thanks in advanced....
Amra korbo joy akhdin............................

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

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

Post by x140l31 » Thu Jul 10, 2008 9:28 pm

Removed after AC
Last edited by x140l31 on Tue Jun 30, 2009 7:34 pm, edited 1 time in total.

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Run Time Error!!!What the....

Post by empo » Thu Nov 13, 2008 5:00 pm

I couldn't find any solution of this run time error till i submitted this 9 times in a row...Plzz suggest where is the error...I suppose RTE occurs due to array bound but it doesn't seem any type of this bound in my solution...
HELLLLLLPPPPPPPPP!!!!!!!!!

Code: Select all

#include<iostream>
using namespace std;

int main()
{
	int result[1000],number=0,num=0,i=0,flag=0,flag1;
	int final[1000];
	
	char ch;
	while(scanf("%c",&ch)!=EOF)
	{
		int end =0;
		if(isspace(ch))
			continue;
		int t = 0,flag1=0;
		for(int k=0;k<1000;k++)
		{
			final[k] = -1;
			result[k] = -1;
		}
		while(1)
		{

			if(t!=0)
				scanf("%c",&ch);
			t++;

			if(isspace(ch))
				continue;
			if(ch=='(')
			{
				flag=0,number=0,num=0,i=0;
				char arr[100];
				for(i=0;i<100;i++)
					arr[i] = ' ';

				scanf("%c",&ch);
				if(ch==')')
				{
					if(t==1)
					end = -1;
					break;
				}
				while(1)
				{
					if(ch==',')
						break;
					else
						num = (ch-'0') + num*10;
					scanf("%c",&ch);
					flag = 1;
				}
				i=0;
				while(1)
				{
					scanf("%c",&ch);
					if(isspace(ch))
						continue;
					if(ch==')')
						break;
					else
						arr[i++] = ch;
				}
				if(arr[0]=='L')
				{
					int temp =1;
					for(int j=0;j<i;j++)
					{
						if(arr[j]=='R')
						{
							for(int k=0;k<=i-1-j;k++)
								number += 2;
							number--;
						}
					}
					for(int k=0;k<i;k++)
						 temp *= 2;
					number = temp + number - 1;
				}
				else if(arr[0]=='R')
				{
					int temp = 1;
					for(int j=0;j<i;j++)
					{
						if(arr[j]=='L')
						{
							for(int k=0;k<=i-1-j;k++)
								number -= 2;
							number++;
						}
					}
					for(int k=0;k<=i;k++)
						temp *= 2;
					number = temp + number - 2 ;
				}
			}
			if(flag==1)
			{
				if(result[number] ==-1)
					result[number] = num;
				else
				{
					//cout<<"repeated node\n";
					flag1 = 1;
				}
			}
			else
				flag1=1;
		}

		int count = 0;
		if(flag1!=1 && end!=-1)
		{
			for(int i=0;i<1000;i++)
			{
				if(result[i]!=-1)
				{
					if(i>0 && result[(i-1)/2]==-1)
					{
						flag1= 1;
						break;
					}
					else
						final[count++] = result[i];
				}
			}
				//cout<<"flag1  "<<flag1<<endl;
		}

		if(flag1!=1 && end!=-1)
		{
			for(i=0;i < count;i++)
				cout<<final[i]<<" ";
		}
		else
			cout<<"not complete";
		cout<<endl;
	}
}
"Accepted" is my passion but RTE is my weakness.....

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Run Time Error!!!What the....

Post by mf » Thu Nov 13, 2008 5:35 pm

empo wrote:.I suppose RTE occurs due to array bound but it doesn't seem any type of this bound in my solution...
Why are you so sure?

You have an array 'char arr[100]', and it seems to me that your program would write beyond its bounds if the input contains a string of L's and R's of length greater than 99.
A valid input file could contain such a string (and judge's input probably does, hence you have the RTE).

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Run Time Error!!!What the....

Post by empo » Thu Nov 13, 2008 5:51 pm

Got my mistake...i jumbled too much in that question.....thanks a lot...Actually i didn't read question very well...
But i admired that quick response..thanks a lot mannn....Fodduuuuuuu
"Accepted" is my passion but RTE is my weakness.....

NeeDay
New poster
Posts: 3
Joined: Mon Feb 16, 2009 10:57 am

I got WA. Though my program is not good, i think it is right

Post by NeeDay » Mon Mar 23, 2009 6:38 pm

I just can't make it right.

Can anybody supply a better way to store the tree?

Besides, i got WA in 0.000, so there must be a case i did consider....

it can make the right answer to the cases in the forum, and also this one:

http://fdemesmay.dyndns.org/cs/acm/v1/122.in

Here is my code, help

Code: Select all

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin("1.in");
    ofstream cout("1.out");
    int start[260] = {0};
    start[1] = 1;
    int temp = 1;
    for(int i = 2; i < 260; i++)
    {
        start[i] = temp + start[i - 1];
        temp *= 2;
    }
    int tree[5000];
    for(int i = 0; i < 5000; i ++)
        tree[i] = -1;
    int avat[5000] = {0};
    int maxc = 0;
    int data;
    char in;
    string inn;
    bool flag = 0;
    while((in = cin.get()) != EOF)
    {
        if(in == '(')
        {
            if((in = cin.get()) == ')')
            {
                if(!flag)
                {
                avat[1] = 1;
                for(int i = 1; i <= maxc; i++)
                    for(int j = 0; j < start[i + 1]; j++)
                    {
                        if(tree[start[i] + j] != -1)
                        {
                            avat[start[i + 1] + 2 * j] = 1;
                            avat[start[i + 1] + 2 * j + 1] = 1;
                        }
                    }
                for(int i = 1; i < start[maxc + 1]; i++)
                {
                    if((tree[i] != -1)&&(avat[i] == 0))
                    {
                        flag = 1;
                        break;
                    }
                }
                }
                if(flag)
                    cout << "not complete" << endl;
                else
                {
                    for(int i = 1; i < start[maxc + 1]; i++)
                    {
                        if(tree[i] != -1)
                        {
                            if(i > 1) cout << " ";
                            cout << tree[i];
                        }
                    }
                    cout << endl;

                }
                for(int i = 0; i < 5000; i ++)
                    tree[i] = -1;
                memset(avat,0,sizeof(avat));
                maxc = 0;
                flag = 0;
            }
            else
            {
                bool tf = 0;
                data = 0;
                while(1)
                {
                    if(in == ',') break;
                    data = data * 10 + in - '0';
                    tf = 1;
                    in = cin.get();
                }
                if(!tf) flag = 1;
                cin >> inn;
                int ceng = inn.length();
                if(ceng > maxc) maxc = ceng;
                int q = 0;
                for(int i = 0; i < ceng - 1; i++)
                {
                    if(inn[i] == 'R')
                    {
                        q += ceng - 1 - i;
                    }
                }
                if(tree[start[ceng] + q] == -1)
                    tree[start[ceng] + q] = data;
                else
                    flag = 1;
            }
        }
    }
    return 0;
}

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

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

Post by mostafa_angel » Sun Nov 01, 2009 4:47 pm

I really Mixed Up...
I Got WA many time but I can not find any mistake in my Code and I think my algorithm is correct too.
help me please...

Code: Select all

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int arr[260];
int arrsize[15];
bool mark[260];
int par[1000];

int s2i(string s)
{
	if(s == "")
		return -2;
	int res = 0;
	for(int i = 0 ; i < s.size() ; i++)
		res+= (s[i] - '0') * pow(10.0 , (double)s.size() - i - 1);
	return res;
}

bool connect(int size)
{
	if(arr[0] > -1)
		mark[0] = true;
	else
		return false;

	for(int i= 1 ; i<= size ; i++)
	{
		if(arr[i] > -1)
		{
			if(mark[par[i]] == false)
				return false;
			else
				mark[i] = true;
		}
	}
	return true;
}

void print(int size)
{
	if(size == 0 && arr[0] == -1)
	{
		cout << "not complete" << endl;
		return;
	}
	if(!connect(size))
	{
		cout << "not complete";
	}
	else
	{
		for(int i = 0 ; i <= size ; i++)
		{
			if(arr[i] > -1)
				cout << arr[i] << " " ;
		}
	}
	cout << endl;
}

int main()
{
	//freopen("in.in","r",stdin);
	string p , n , po;
	int size = 0 , pos , num; 
	bool rep = false;
	
	arrsize[1] = 2;
	for(int i = 2 ; i < 15 ; i++)
		arrsize[i] = arrsize[i-1]+pow(2.0 , i);

	memset(arr , -1 , sizeof arr);
	memset(mark , false , sizeof mark);
	int cnt = 0;
	for(int i = 1 ; i < 1000 ; i++)
	{
		par[i] =cnt; 
		if(i % 2 == 0)
			cnt++;
	}

	while(cin >> p)
	{
		n.clear();
		po.clear();
		if(p == "()")
		{
			if(!rep)
				print(size);
			else
			{
				arr[0] = -1;
				print(0);
			}
			memset(arr , -1 , sizeof arr);
			memset(mark , false, sizeof mark);
			size = 0;
			rep = false;
			continue;
		}
		else
		{
			int i;
			for(i = 1 ; i < p.size() ; i++)
			{
				if(p[i] == ',')
					break;
				else
					n+= p[i];
			}
			i = p.find(",");

			for(i = i+ 1 ; i < p.size() - 1 ; i++)
				po+= p[i];
			num = s2i(n);
			size = max(arrsize[po.size()] , size);
			if(po.size() == 0)
			{
				if(arr[0] != -1)
					rep = true;
				else
					arr[0] = num;
			}
			else
			{
				pos = 0;
				for(i = po.size() -1 ; i >= 0 ; i--)
				{
					if(po[i] == 'L')
						pos+=pow(2.0 , (double)po.size() - i -1);
					else
						pos+=pow(2.0 ,(double) po.size() - i);
				}
				if(arr[pos] != -1)
					rep = true;
				else
					arr[pos] = num;
			}
		}
	}
	return 0;
}

shadowdude04
New poster
Posts: 2
Joined: Tue Feb 23, 2010 11:16 pm

122 - Trees on the level .. keep getting WA

Post by shadowdude04 » Tue Feb 23, 2010 11:31 pm

Hi,
I've gotten an assignment where i am suppose to implement an algorithm for problem 122 (Trees on the level) in Java, i've now tested my program for many hours and have always gotten the expected output.
The problem is the online judge won't accept my answer (says Wrong Answer) so i would really appreciate some help.

Here's my code:

Code: Select all

import java.io.*;
import java.text.CharacterIterator;
import java.text.StringCharacterIterator;
import java.util.ArrayList;

class Main{
	public static void main(String args[])
	{
		TreesOnTheLevel solver = new TreesOnTheLevel();
		solver.run();
	}
}
class TreesOnTheLevel implements Runnable 
{
	private BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	ArrayList<String> outputs = new ArrayList<String>();
	String temp;

	public void run(){
		try {
		boolean endOfTree = false;
		boolean fail = false;
		String[] treeValues = new String[256];
			while(!endOfTree)
			{
			String treeLine = input.readLine();
			String[] nodes = treeLine.split(" ");
			
			if(nodes[nodes.length-1].compareTo("()")==0)
			endOfTree = true; 
			
			
				for(int i=0; i<nodes.length; i++)
				{
					String[] locations = nodes[i].split(",");
					for(int j=1; j < locations.length; j+=2 )
					{
						if (locations[j].compareTo(")")==0)
						{
						    if(treeValues[0] != null)
						 	{
						 		fail = true;
						 	}
						    else     
						    {
						    	treeValues[0] = locations[j-1].substring(1);
						    }
						}
			
						
						else {		
						CharacterIterator it = new StringCharacterIterator(locations[j]);
						int count = 1;
						for (char ch = it.first(); ch != CharacterIterator.DONE; ch = it.next())
						{
							if(ch == 'L')
								count *=2;
							else if(ch == 'R')
								count = (count * 2)+1;
						}
						locations[j-1]=locations[j-1].substring(1);
						 	if(treeValues[count-1] != null)
						 	{
						 		fail = true;
						 	}
						 	else
							treeValues[count-1] = locations[j-1];
						 	
							}
					}
				}
			
			}
			
			temp = null;
			
			if(!fail && isValid(treeValues))
			{
				temp = treeValues[0];
				for(int i=1; i<256; i++)
				{
					if(treeValues[i] != null)
					temp = temp + (" " + treeValues[i]);
				}
			}
			else 
			{
				temp = "not complete";
			}
			outputs.add(temp);
			
				run();

	} catch (Exception IOException) {
        printIt();
	} 
	
	}
	public boolean isValid(String[] values)
	{
		if (values[0]==null)
			return false;
		for(int i = 255; i > 0; i--)
		{
			if(values[i]!=null && values[(i-1)/2] == null)
				return false;
		}
		return true;
	}
	public void printIt()
	{
		for(String i : outputs)
			if(i != null)
			System.out.println(i);
	}
}
Since the program should terminate at "end-of-file" i choose to print all the outputs when an exception is thrown hence there is no more lines in the file.

This is the first time i use the online judge so i really have no idea why it gives me a "wrong answer"

shadowdude04
New poster
Posts: 2
Joined: Tue Feb 23, 2010 11:16 pm

122 - Trees on the level .. keep getting WA

Post by shadowdude04 » Tue Feb 23, 2010 11:33 pm

Hi,
I've gotten an assignment where i am suppose to implement an algorithm for problem 122 (Trees on the level) in Java, i've now tested my program for many hours and have always gotten the expected output.
The problem is the online judge won't accept my answer (says Wrong Answer) so i would really appreciate some help.

Here's my code:

Code: Select all

import java.io.*;
import java.text.CharacterIterator;
import java.text.StringCharacterIterator;
import java.util.ArrayList;

class Main{
	public static void main(String args[])
	{
		TreesOnTheLevel solver = new TreesOnTheLevel();
		solver.run();
	}
}
class TreesOnTheLevel implements Runnable 
{
	private BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	ArrayList<String> outputs = new ArrayList<String>();
	String temp;

	public void run(){
		try {
		boolean endOfTree = false;
		boolean fail = false;
		String[] treeValues = new String[256];
			while(!endOfTree)
			{
			String treeLine = input.readLine();
			String[] nodes = treeLine.split(" ");
			
			if(nodes[nodes.length-1].compareTo("()")==0)
			endOfTree = true; 
			
			
				for(int i=0; i<nodes.length; i++)
				{
					String[] locations = nodes[i].split(",");
					for(int j=1; j < locations.length; j+=2 )
					{
						if (locations[j].compareTo(")")==0)
						{
						    if(treeValues[0] != null)
						 	{
						 		fail = true;
						 	}
						    else     
						    {
						    	treeValues[0] = locations[j-1].substring(1);
						    }
						}
			
						
						else {		
						CharacterIterator it = new StringCharacterIterator(locations[j]);
						int count = 1;
						for (char ch = it.first(); ch != CharacterIterator.DONE; ch = it.next())
						{
							if(ch == 'L')
								count *=2;
							else if(ch == 'R')
								count = (count * 2)+1;
						}
						locations[j-1]=locations[j-1].substring(1);
						 	if(treeValues[count-1] != null)
						 	{
						 		fail = true;
						 	}
						 	else
							treeValues[count-1] = locations[j-1];
						 	
							}
					}
				}
			
			}
			
			temp = null;
			
			if(!fail && isValid(treeValues))
			{
				temp = treeValues[0];
				for(int i=1; i<256; i++)
				{
					if(treeValues[i] != null)
					temp = temp + (" " + treeValues[i]);
				}
			}
			else 
			{
				temp = "not complete";
			}
			outputs.add(temp);
			
				run();

	} catch (Exception IOException) {
        printIt();
	} 
	
	}
	public boolean isValid(String[] values)
	{
		if (values[0]==null)
			return false;
		for(int i = 255; i > 0; i--)
		{
			if(values[i]!=null && values[(i-1)/2] == null)
				return false;
		}
		return true;
	}
	public void printIt()
	{
		for(String i : outputs)
			if(i != null)
			System.out.println(i);
	}
}
Since the program should terminate at "end-of-file" i choose to print all the outputs when an exception is thrown hence there is no more lines in the file.

This is the first time i use the online judge so i really have no idea why it gives me a "wrong answer"

Blocat
New poster
Posts: 2
Joined: Sat Jul 24, 2010 5:25 am

122 Trees on the level...Wrong answer

Post by Blocat » Wed Sep 08, 2010 6:25 am

I have read every threads about 122, but got wrong answer again and again. :(

I guess the problem is from "not complete" case. And to my understand, the "not complete" should be printed when one input data has the following cases:
  • nodes without parents
    nodes with two values, like (1,) and (2,)
    no nodes
    (,)
    nodes without values, like (,LLL)
I tried the input data found in the previous threads and compare my result with that of http://uvatoolkit.com/problemssolve.php. It seems OK for both of the results, except uvatoolkit print a blank line when the input data has () only (but I print "not complete" instead).

The following is my code with the comments. Really hope someone can help me out. :cry:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
	char s[10000];	/* store a pair (n,s) */
	unsigned int a[16384] = {};	/* store the binary tree with max depth of 14 */
	char *v, *p;
	int i, ind, flag = 0; 

	while (scanf("%s", s) == 1) {				/* read one pair*/
		if ((v = strtok(s, "(),")) == NULL) {	/* if "()", read out the tree */
			if (strlen(s) == 3) {				/* if "(,)", print "not complete" later */
				flag = 1;
				continue;
			}

			/* if the tree is not complete, raise the flag */
			for (i = 2; i < 256; i++) if (a[i] != 0 && a[i/2] == 0) flag = 1;	/* no parent */
			if (a[1] == 0) flag = 1;	/* no root */

			if (flag == 1) 	/* it means the tree is not complete when flag is on*/
				printf("not complete\n");
			else {		/* otherwise, traverse the tree */
				printf("%d", a[1]);
				for (i = 2; i < 256; i++) if (a[i] != 0) printf(" %d", a[i]);
				printf("\n");
			}

			bzero(a, sizeof(a));	/* clean the tree */
			flag = 0;	/* clean the flag */
			continue;	/* read next pair */
		}

		if (!isdigit(v[0])) { 	/* for cases like (,LLL) */
			flag = 1;
			continue;
		}

		if ((p = strtok(NULL, "(),")) == NULL) {	/* if root, store its value in a[1] */
			ind = 1;
		} else {	/* otherwise, calculate the index of the node */
			for (i = 0, ind = 1; p[i] != '\0'; i++)
				ind = (p[i] == 'L') ? (ind*2) : (ind*2+1);
		}
	
		if (a[ind] == 0)	/* if the node doesn't have a value yet, store it */
			a[ind] = atoi(v);
		else	/* otherwise, raise the flag to print "not complete" later */
			flag = 1;
	}

	return 0;
}

ghooo
New poster
Posts: 3
Joined: Tue Sep 01, 2009 2:13 pm

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

Post by ghooo » Tue Jul 12, 2011 7:31 am

very helpful input, thanks man

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm
Location: Manikgonj, Bangladesh

Post by ?????? ???? » Mon Sep 17, 2012 12:16 am

Code: Select all

Remove
Last edited by ?????? ???? on Sun Nov 24, 2013 4:19 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Tue Sep 18, 2012 10:35 pm

Make your tree array bigger. Size 20,000 is big enough.
Check input and AC output for thousands of problems on uDebug!

gfv
New poster
Posts: 6
Joined: Wed Jun 26, 2013 3:23 am

WA on Problem #122

Post by gfv » Wed Jun 26, 2013 3:28 am

I keep getting WA on this problem, but I can't find a problem on my algorithm.

Here's my code:
http://pastebin.com/d6Xc7DP1

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define NUM_NODES 256

template <class T>
class Tree
{
private:
	T heap[NUM_NODES];
	int hs[NUM_NODES];	// HeapStatus - 0: Não Setado; 1: Setado; 2: Não setado com filho
	bool errflag;
	int iCount;
	int eCount;
public:
	Tree()
	{
		this->errflag = false;
		this->iCount = 0;
		memset(this->heap, 0, NUM_NODES);
		memset(this->hs, 0, NUM_NODES);
	}

	void insert(T content, char* dir);
	void readTree();
	bool isEmpty();
	void setInvalid();
};

template <class T>
void Tree<T>::insert(T content, char* dir)
{
	int aux = 1;
	for(int i = 0; dir[i] != '\0'; i++)
	{
		// Nó da direita, posição 2n + 1
		if(dir[i] == 'R')
		{
			aux *= 2;
			aux += 1;
		}
		// Nó da esquerda, posição 2n 
		else if(dir[i] == 'L')
		{
			aux *= 2;
		}
	}

	// Verifica se o nó inserido é filho de um nó não setado.
	if(aux%2 && (aux - 1) && !this->hs[(aux - 1)/2 - 1])
	{
		this->hs[(aux - 1)/2 - 1] = 2;
		this->iCount++;
	} else if(!(aux%2) && !this->hs[aux/2 - 1])
	{
		this->hs[aux/2 - 1] = 2;
		this->iCount++;
	}

	// Se o nó não foi setado e não tem filhos setados.
	if(!this->hs[aux - 1])
	{
		this->heap[aux - 1] = content;
		this->hs[aux - 1] = 1;
		this->eCount++;      
	} 
	
	// Se o nó não foi setado mas tem filho setado.
	else if(this->hs[aux - 1] == 2)
	{
		this->heap[aux - 1] = content;
		this->hs[aux - 1] = 1;
		this->iCount--;
		this->eCount++;
	} else this->errflag = true;	// Se o nó já havia sido setado.
}

template <class T>
void Tree<T>::readTree()
{
	if(!this->errflag && !this->iCount)
	{
		for(int i = 0; i < 256; i++)
		{
			if(this->hs[i])
			{
				this->eCount--;
				if(this->eCount)
					printf("%d ", (int) this->heap[i]);
				else
					printf("%d", (int) this->heap[i]);
			}
		}
		printf("\n");
	} else printf("not complete\n");
}

template <class T>
bool Tree<T>::isEmpty()
{
	return !((bool) this->eCount);
}

template <class T>
void Tree<T>::setInvalid()
{
	this->errflag = true;
}

int main()
{
	Tree<unsigned long> *tree;
	char buf[32];
	unsigned long i_buf;

	while(scanf("%s", buf) > 0)
	{
		tree = new Tree<unsigned long>();
		while(strcmp(buf, "()"))
		{
			i_buf = 0;
			for(int i = 1; buf[i] != ','; i++)
			{
				if(buf[i] == '-')
				{
					tree->setInvalid();
					break;
				}
				if((buf[i] >= '0')&&(buf[i] <= '9'))
				{
					i_buf = i_buf*10 + (buf[i] - '0');
				}
			}
			if(!i_buf) tree->setInvalid();
			else tree->insert(i_buf, buf);
			scanf("%s", buf);
		}
		if(!tree->isEmpty()) tree->readTree();
		else printf("not complete\n");
		delete tree;
	}

	return 0;
}
I've tried the following input:

Code: Select all

()
(,) ()
(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 was:

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
Which seems about right to me.

I'd be glad if anyone could help me.
Thanks.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA on Problem #122

Post by brianfry713 » Thu Jun 27, 2013 12:34 am

Try input:
(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) ()
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”