OJ Board

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

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

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

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

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

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

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

Code: Select all

Remove

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

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

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