miércoles, diciembre 15, 2010

Suma de Árbol - Problema UVA 112 - Versión 2

Esta nueva versión trata de mejorar el desempeño reemplazando el uso de StringBuffers por operaciones con Strings, pero sigue dando más de los tres segundos en la evaluación de UVA:

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 = "";
        String         linea = null;
        final int       SIZE = 256;
        int    valorBusqueda = 0;
        int[]          arbol;
        int[]          sumas;
        Scanner        input = null;
        while(true) {
            linea = in.readLine();
            if(linea==null) break;
            archivo+=linea;
        }
        while(archivo.length()>0) {
            input             = new Scanner(archivo);
            valorBusqueda     = input.nextInt();
            archivo           = archivo.replaceFirst(valorBusqueda+"","");
            String tmpCadena  = getCadena(archivo);
            archivo           = archivo.substring(tmpCadena.length());
            arbol             = new int[SIZE];
            sumas             = new int[SIZE];
            procesar(tmpCadena, arbol, sumas, 0);
            if(buscar(valorBusqueda, sumas)) System.out.println("yes");
            else System.out.println("no");
        }
    }

    void procesar(String cadena, int[] arbol, int[] sumas, int nodo) {
       if(cadena.matches("\\s*\\(\\s*\\)")) return;
       cadena        = cadena.trim().substring(1,cadena.length()-1);
       String numStr = "";
       int       pos = 0;
       while(cadena.charAt(pos)!='(') numStr+=cadena.charAt(pos++);
       cadena       = cadena.substring(numStr.length());
       arbol[nodo]  = Integer.parseInt(numStr.trim());
       sumas[nodo]  = arbol[nodo]+sumas[(nodo-1)/2];
       String h1Str = getCadena(cadena);
       cadena       = cadena.substring(h1Str.length());
       h1Str        = h1Str.trim();
       String h2Str = getCadena(cadena);
       cadena       = cadena.substring(h2Str.length());
       h2Str        = h2Str.trim();
       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(String sb) {
        int       numIzq = 0;
        int          pos = 0;
        String respuesta = "";
        do {
            while (sb.charAt(pos) == ' ') respuesta += sb.charAt(pos++);
            if (sb.charAt(pos) == '(') numIzq++;
            if (sb.charAt(pos) == ')') numIzq--;
            respuesta += sb.charAt(pos++);
        } while (numIzq > 0);
        return respuesta;
    }

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

0 comentarios:

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar