martes, diciembre 14, 2010

Suma de Árbol - Problema UVA 112

En este problema se ingresan uno o varios árboles binarios en notación de lenguaje LISP y se espera determinar si alguna de las ramas que inician en la raiz y terminan en una hoja suman un valor dado para cada árbol.

El enunciado se encuentra en la dirección http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=48


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

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        String archivo = "";
        while(true) {
            String linea = in.readLine();
            if(linea==null) break;
            archivo+=linea;
        }
        while(archivo.length()>0) {
            Scanner input = new Scanner(archivo);
            int valorBusqueda = input.nextInt();
            archivo = archivo.replaceFirst(valorBusqueda+"","");
            StringBuffer tmp = new StringBuffer(archivo);
            String tmpCadena = getCadena(tmp);
            int[]   arbol = new int[256];
            int[]   sumas = new int[arbol.length];
            //System.out.println(tmpCadena);
            procesar(tmpCadena, arbol, sumas, 0);
            if(buscar(valorBusqueda, sumas)) System.out.println("yes");
            else System.out.println("no");
            archivo = tmp.toString();
        }
    }

    void procesar(String cadena, int[] arbol, int[] sumas, int nodo) {
       if(cadena.matches("\\(\\s*\\)")) return;
       cadena = cadena.trim();
       StringBuffer tmp1 = new StringBuffer(cadena);
       tmp1.deleteCharAt(tmp1.length()-1);
       tmp1.deleteCharAt(0);
       String numStr = "";
       while(tmp1.charAt(0)!='(') { numStr+=tmp1.charAt(0); tmp1.deleteCharAt(0); }
       arbol[nodo]=Integer.parseInt(numStr);
       sumas[nodo]=arbol[nodo]+sumas[(nodo-1)/2];
       String h1Str = getCadena(tmp1);
       String h2Str = getCadena(tmp1);
       procesar(h1Str, arbol, sumas, 2*nodo+1 );
       procesar(h2Str, arbol, sumas, 2*nodo+2 );
       if(sumas[2*nodo+1]>0 || sumas[2*nodo+2]>0) sumas[nodo]=0;
    }

    String getCadena(StringBuffer sb) {
       int       numIzq = 0;
       String respuesta = "";
       do {
           while(sb.charAt(0)==' ') sb.deleteCharAt(0);
           if(sb.charAt(0)=='(') numIzq++;
           if(sb.charAt(0)==')') numIzq--;
           respuesta+=sb.charAt(0);
           sb.deleteCharAt(0);
       } while(numIzq>0);
        return respuesta;
    }

    boolean buscar(int valor, int[] vector) {
        for(int x: vector) if(valor==x) return true;
        return false;
    }
}


Esta solución funciona con todos los casos de prueba pero se excede en el tiempo máximo de evaluación de tres segundos. Se esperan comentarios y sugerencias.

0 comentarios:

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar