TÓPICO

PROBLEM 1195 - URI Fórum 1.0

URI Online Judge perguntou 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

  • Bruno Camargo respondido 6 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");
    
            }
    
        }
    }
  • Victor Hugo Braguim Canto respondido 5 years ago

    [RESOLVIDO]

  • Unknown respondido 4 years ago

    Estou tomando Runtime Error, e não faço ideia do que seja. tinha colocado o tamanho da arvore de 2000, o que equivale a 4*maxn nesse problema, ai tomei runtime e mudei pra 1kk só pra testar, mas continua. Alguem poderia me ajudar?

    #include <bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    ll btree[1000000];
    
    void prefixa(ll root){
        if(btree[root] == -1)   return;
        cout << " " << btree[root];
        prefixa(root*2);
        prefixa(root*2+1);
    }
    
    void infixa(ll root){
        if(btree[root] == -1)   return;
        infixa(root*2);
        cout << " " << btree[root];
        infixa(root*2+1);
    }
    
    void posfixa(ll root){
        if(btree[root] == -1)   return;
        posfixa(root*2);
        posfixa(root*2+1);
        cout << " " << btree[root];
    
    }
    
    void insert(ll no, ll root){
        if(btree[root] == -1){
            btree[root] = no;
            return;
        }
        if(btree[root] >= no){
            insert(no, root*2);
        }
        else{
            insert(no, (root*2)+1);
        }
        return;
    }
    int main(){
        ll c, n, no;
        cin >> c;
        for(ll i=1; i<=c; i++){
            cin >> n;
            memset(btree, -1, sizeof btree);
            while(n--){
                cin >> no;
                insert(no, 1);
            }
            cout << "Case " << i << ":" << endl;
            printf("Pre.:");    prefixa(1);     printf("\n");
            printf("In..:");    infixa(1);      printf("\n");
            printf("Post.:");   posfixa(1);     printf("\n");
        }
    }
  • Victor Hugo Braguim Canto respondido 4 years ago

    Obrigado, Igor! Foi exatamente isso! =D

  • Unknown respondido 4 years ago

    Cara, eu também recebi WA40% e por incrível que pareça eu estava dando a saída do mesmo jeito que você. Na verdade, é só corrigir para:

      **printf("Pre.: ");**
    
       **printf("In..: ");**
    
       **printf("Post: ");**
  • Pablo Freire respondido 6 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);
                }
            }
        }
    }
  • Caíque de Castro respondido 7 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.

  • Grace Ellen respondido 7 years ago

    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

  • Joe respondido 7 years ago

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

  • Jefe respondido 7 years ago

    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.

  • Joe respondido 7 years ago

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