TEMA

PROBLEM 1195 - URI Fórum 1.0

beecrowd preguntado on feb 8 2013

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • bcamargo respondido 9 years ago

    O que está errado neste código? Sei que é chato fazer uma pergunta genérica dessa, mas eu já testei até com intervalo [0, 499] e bateu com o toolkit. Porém ainda por Time limit exceeded. Alguém pode pensar em uma entrada que bug este código? As funções foram retiradas do livro do Deitel. 

    import java.io.*;
import java.util.*;

public class Main{
    static int flag = 0;
    static class TreeNode < T extends Comparable < T> >{

        // membros de acesso de pacote
        TreeNode< T > leftNode; // nó esquerdo
        T data; // valor do nó
        TreeNode< T > rightNode; //nó direito

        // construtor inicializa os dados e os torna um nó de folha
        public TreeNode( T nodeData){
            data = nodeData;
            leftNode = rightNode = null; // o nó não tem filho
        } // fim do construtor Treenode

        // localiza ponto de inserção e insere novo nó; ignora valores duplicados
        public void insert( T insertValue ){
            //insere na subárvore esquerda
            if( insertValue.compareTo( data ) < 0 ){
                //insere novo TreeNode
                if( leftNode == null )
                    leftNode = new TreeNode< T >(insertValue);
                else // continua percorrendo a subárvore esquerda recursivamente
                    leftNode.insert( insertValue );
            } //fim do if

            //insere na subárvore direita
            else if(    insertValue.compareTo( data ) > 0 ){
                //insere novo TreeNode
                if( rightNode == null )
                    rightNode = new TreeNode< T >(insertValue);
                else // continua percorrendo a subárvore esquerda recursivamente
                    rightNode.insert( insertValue );
            } //fim do else if  
        } //fim do método insert
    } //fim da classe Treenode

    // definição da classe Tree
    public static class Tree< T extends Comparable < T > >{
        private TreeNode < T > root;

        // contrusto inicializa uma Tree de inteiros vazia
        public Tree(){
            root = null;
        } // fim do construtor sem argumentos Tree

        //insere um novo nó na árvore de pesquisa binária
        public void insertNode( T insertValue ){
                if( root == null )
                    root = new TreeNode< T >( insertValue); //cria o nó raiz
                else
                    root.insert( insertValue); // chama o método insert
        } // fim do método insertNode

        //inicia percurso na pós-ordem
        public void postorderTraversal(){
            postorderHelper( root );
        } // fim do método postorderTraversal

        //incia o percurso da pré-ordem
        private void preorderTraversal(){
            preorderHelper( root );
        } // fim do método preorderTraversal

        //inicia o percurso na ordem infixa 
        private void inorderTraversal(){
            inorderHelper( root );
        }//fim do método inorderTraversal

        // método recursivo para realizar o percurso infixo
        private void inorderHelper( TreeNode< T > node ){
            if( node == null )
                return;
            inorderHelper( node.leftNode );
            if( flag == 0 ){
                System.out.printf( "%s",node.data );
                flag = 1;
            }
            else
                System.out.printf( " %s",node.data );
            inorderHelper( node.rightNode );
        }//fim do método inorderHelper

        // método recursivo para realizar percurso na pré-ordem
        private void preorderHelper( TreeNode< T > node ){
            if( node == null )
                return;
            if( flag == 0 ){
                System.out.printf( "%s",node.data );
                flag = 1;
            }
            else
                System.out.printf( " %s",node.data );
            preorderHelper( node.leftNode );
            preorderHelper( node.rightNode );
        }//fim do método preorderHelper

        //método recursivo para realizar percurso na pós-ordem
        public void postorderHelper( TreeNode< T > node ){
            if ( node == null )
                return;
            postorderHelper( node.leftNode  ); //percorre subárvore esquerda
            postorderHelper( node. rightNode ); // percorre subárvore direita
            if( flag == 0 ){
                System.out.printf( "%s",node.data );
                flag = 1;
            }
            else
                System.out.printf( " %s",node.data );
        } // fim do método postorderHelper
    }// fim da classe Tree

    public static void main(String args[]) throws IOException {

        BufferedReader l = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Tree < Integer > tree;
        int value, cases, i, elements,k = 0;    
        String[] row;

        cases = Integer.parseInt( l.readLine() );
        while(  cases -- > 0 ){
            tree = new Tree < Integer >();
            k++;
            elements = Integer.parseInt( l.readLine() );
            row = l.readLine().split(" ");
            for(i = 0; i < elements; i++ ){
                value = Integer.parseInt(row[i]);
                tree.insertNode( value );
            }
            System.out.println( "Case "+k+":");
            System.out.printf( "Pre.: " );
            tree.preorderTraversal();
            flag = 0;
            System.out.printf("\n");
            System.out.printf("In..: ");
            tree.inorderTraversal();
            flag = 0;
            System.out.printf("\n");
            System.out.printf("Post: ");
            tree.postorderTraversal();
            flag = 0;
            System.out.printf("\n\n");

        }

    }
}

  • vhbcanto respondido 8 years ago

    [RESOLVIDO]

  • vhbcanto respondido 7 years ago

    Obrigado, Igor! Foi exatamente isso! =D

  • pfreire0 respondido 9 years ago

    o meu código está muito parecido com o de Bruno Camargo. Também está dando TLE. Alguém pode me dar uma dica sobre a possível causa?

    import java.io.IOException;
import java.util.Scanner;

/**
 *
 * @author Pablo
 */
public class Main {

    static int flag = 0;

    static class No {

        int valor;
        No esquerda;
        No direita;

        public No(int valor) {
            this.valor = valor;
        }
    }

    public static void main(String[] args) throws IOException {
        new Main().executar();
    }

    private void executar() {
        Scanner ent = new Scanner(System.in);
        int teste = ent.nextInt();
        for (int i = 0; i < teste; i++) {
            int n = ent.nextInt();
            No raiz = new No(ent.nextInt());
            for (int j = 0; j < n - 1; j++) {
                inserir(raiz, ent.nextInt());
            }
            System.out.println("Case " + (i + 1) + ":");
            System.out.print("Pre.: ");
            prefixado(raiz);
            flag = 0;

            System.out.print("\nIn..: "); 
            emordem(raiz); 
            flag = 0;

            System.out.print("\nPost: ");
            posfixado(raiz); 
            flag = 0;

            // Para não dar presentation error na URI
            if (i == teste - 1) {
                System.out.println("");
            } else {
                System.out.println("\n");
            }
        }
    }

    private void inserir(No node, int valor) {
        //Verifica se o valor a ser inserido é menor que o nodo corrente da árovre, se sim vai para subarvore esquerda
        if (valor < node.valor) {
            //Se tiver elemento no nodo esquerdo continua a busca
            if (node.esquerda != null) {
                inserir(node.esquerda, valor);
            } else {
                //Se nodo esquerdo vazio insere o novo nodo aqui
                // System.out.println("\tInserindo " + valor + " a esquerda de " + node.valor);
                node.esquerda = new No(valor);
            }
            //Verifica se o valor a ser inserido é maior que o nodo corrente da árvore, se sim vai para subarvore direita
        } else if (valor > node.valor) {
            //Se tiver elemento no nodo direito continua a busca
            if (node.direita != null) {
                inserir(node.direita, valor);
            } else {
                //Se nodo direito vazio insere o novo nodo aqui
                // System.out.println("\tInserindo " + valor + " a direita de " + node.valor);
                node.direita = new No(valor);
            }
        }
    }

    private void prefixado(No no) {
        if (no != null) {
            if (flag == 0) {
                System.out.printf("%s", no.valor);
                flag = 1;
            } else {
                System.out.printf(" %s", no.valor);
            }
            if (no.esquerda != null) {
                prefixado(no.esquerda);
            }
            if (no.direita != null) {
                prefixado(no.direita);
            }
        }
    }

    private void emordem(No no) {
        if (no != null) {
            if (no.esquerda != null) {
                emordem(no.esquerda);
            }
            if (flag == 0) {
                System.out.printf("%s", no.valor);
                flag = 1;
            } else {
                System.out.printf(" %s", no.valor);
            }
            if (no.direita != null) {
                emordem(no.direita);
            }
        }
    }

    private void posfixado(No no) {
        if (no != null) {
            if (no.esquerda != null) {
                posfixado(no.esquerda);
            }
            if (no.direita != null) {
                posfixado(no.direita);
            }
            if (flag == 0) {
                System.out.printf("%s", no.valor);
                flag = 1;
            } else {
                System.out.printf(" %s", no.valor);
            }
        }
    }
}

  • Joe101 respondido on jun 25 2013

    Recebi accepted valeu a ajuda era o ultimo espaco que faltava no main kk

  • Joe101 respondido on jun 25 2013

    A não uai o que que tem de errado no meu programa da arvore tá perfeita a saída uai , to recebendo presentation error !!!

    int main (void){
    int op,testes,cont=0,testeSupremo;
    raiz=NULL;

    cin>>testeSupremo;

    while(testeSupremo > 0){

    cin>>testes;

    while(testes > 0){

        incluir();

     testes--;
    }
.......

  • cdcastro respondido 9 years ago

    Grace, o erro Time limit exceeded corresponde que o algoritmo não foi aceito dentro do tempo. Não significa necessariamente que a resposta esteja incorreta.

  • gellen respondido on abr 25 2014

    Boa noite, Estou submetendo o problema 1195, porém está dando Time limit exceeded. Já realizei diversos casos de testes e todos corresponderam ao resultado. Fiz algumas modificações, entretanto isso persiste ... Não vejo mais o que modificar ...

    PS: submissão em java

  • jefetiepo respondido on jun 25 2013

    Riposa,

    Presentation error, significa que seu algoritmo esta certo, mas esta faltando alguma coisa na saída, como por exemplo um espaço ou uma quebra de linha, olha a observação no final da especificação de saída:

    Obs: Não deve haver espaço em branco após o último item de cada linha e há uma linha em branco após cada caso de teste, inclusive após o último.

    Seu algoritmo não imprime uma linha depois de cada caso de teste.