Bueno aqui posteo la solución del ejercicio de las raices cuadradas, no es tan eficiente pero fue aceptado en el juez tarda mas o menos 1.2 segundos, se puede mejorar bastante a momento de leer los datos, creo se pude utilizar una arreglo de chars, pero bueno ... se debe codificar un poco más ... tengo 8 versiones ... las primeras fuerón rechazadas por limite de tiempo, pero esta versión es bastante aceptable ...
/** Clase ReverseRoot8.java
* Autor Wilfredo Vargas Almendras
* Fecha 02/03/2007
* Hora 07:13:04 PM
* Proyecto Yachay Wasej Punkun
*
*/
import java.text.DecimalFormat;
import java.util.HashMap;
import java.util.Scanner;
public class ReverseRoot8 {
static HashMap<Long,String> raices = new HashMap<Long, String>();
static long[] numeros = new long[262144];
static Scanner lector = new Scanner(System.in);
static DecimalFormat formateador = new DecimalFormat("####.####");
public static void main(String[] args) {
long sig;
int contador = 0;
while( lector.hasNext()){
sig = lector.nextLong();
numeros[contador++] = sig;
}
StringBuffer res = new StringBuffer(contador);
for (int i = contador-1; i >= 0; i--)
res.append( siguienteRaiz( numeros[i] )+"\n");
System.out.println(res);
}
private static String siguienteRaiz(Long indice) {
String res="";
res = raices.get(indice);
if( res == null ){
res = calcularRaiz(indice);
raices.put(indice, res);
}
return res;
}
private static String calcularRaiz(Long indice) {
String res;
long raiz = (long)(Math.sqrt(indice)*100000);
if( raiz/100000.0 == raiz/100000 )
res = raiz/100000+".0000";
else
res = ""+formateador.format(raiz/100000.0+0.00005);
return res;
}
}
Ahora un problema interesante, se trata de un arbol genealógico, creo la solución más sencilla seria armando todo el "arbol" (grafo), pero creo se puede hacer de alguna otra forma más eficiente. Espero opiniones y otras soluciones :). Tanto de las raices como este del árbol genealógico.. Si pueden mejorar mi código... posteenlo, sera bueno tener alguna versión bastante optima.. :)
Palabras clave: concurso programación, ejercicios, problemas
Comentarios
Acá hay métodos para sacar raíces por aproximación, pero creo que no es necesario para este problema: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
En python:
#!/usr/bin/env python import sys from math import sqrt data = [] # empty data for line in sys.stdin: data = data + line.split() # add elements to data # use list generators #print [ sqrt(float(n)) for n in reversed(data) ] for n in reversed(data): print '%.4f' % sqrt(float(n))Con un input de 10000 números 1000000000000000000, osea 200Kbytes:
rolando@boo:~$ time cat 1001.test.2 |python 1001.reverse-root.py > /dev/null
real 0m1.310s
user 0m1.252s
sys 0m0.020s
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ....
cada vez estarias calculando la raiz de 1000, eso me parece innecesario hacer tal tarea, mas bien se deberia reutilizar lo que ya se ha calculado. No se si python almacena los resultados ya calculados (sacame de dudas), algo asi como en haskell (almacenando en celdas). Pero bueno ... la solucion simple sirve ... la cosa seria implementarlo en un lenguaje que se pueda enviar al juez y probar si acepta :)
Que tal Wilfredo,
tengo una consulta respecto al problema de reverseRoot,
¿como controlo "A size of the input stream does not exceed 256 KB"?
Existe alguna forma de controlar que el tamaño del stream no exceda a 256 KB,
tal parece que tu codigo no controla esto, o ¿como lo interpretaste tu?
Buen punto de vista wilfredo.
Proximamente estare colocando mas ejercicios, pues ya que se hacerca el concurso. Wilfredo no te olvides de revizar este post.