Ir al contenido (saltar navegación)

Las dimensiones del puzzle

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Empezando un puzzle enorme

Los puzzles son un pasatiempo que consiste en reconstruir una figura uniendo correctamente las diferentes partes que la componen, normalmente pequeñas piezas planas que encajan unas con otras. La cantidad de piezas de las que se componga el puzzle es una indicación de su complejidad. También lo es la imagen que contiene; las zonas con un color uniforme son mucho más difíciles de montar, al no tener ayuda sobre qué pieza va junto a qué otra.

Cualquiera que haya montado un puzzle alguna vez sabe que lo más sencillo es comenzar buscando las piezas que forman los laterales, para construir el borde externo. Se empieza buscando las piezas que son planas en alguno de sus lados y una vez recopiladas se encajan hasta formar el marco. En este segundo paso, resulta muy útil conocer el número de piezas a lo ancho y a lo alto que tiene el puzzle.

Por fin vas a empezar a montar el puzzle que te regalaron hace varios años y quieres saber sus dimensiones. Conoces el número total de piezas, dado que lo indica la caja. Suponiendo que el ancho y el alto son lo más parecido posible, ¿eres capaz de averiguar la longitud del lado más largo sabiendo que no sobra ni falta ninguna pieza?

Entrada

El programa leerá de la entrada estándar múltiples casos de prueba, uno por línea. Cada caso de prueba consta de un número positivo menor o igual que 109 indicando el número total de piezas del puzzle.

La entrada termina con un puzzle sin piezas, que no deberá procesarse.

Salida

El programa escribirá en la salida estándar, para cada caso de prueba, la longitud del lado más largo del puzzle correspondiente.

Recuerda que si hay varias posibles respuestas, se dará aquella en la que la distancia entre el ancho y el alto sea mínima.

Entrada de ejemplo

1000
2000
500
0

Salida de ejemplo

40
50
25