Problema número 357

La prueba de las cajas y las bolas

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Persona hundida entre bolas

En un concurso de televisión los concursantes deben superar una prueba de rapidez. En un lado del estudio, N cajas. En el otro lado un tanque lleno de bolas de plástico. Lo que tienen que hacer es ir corriendo al depósito de bolas, recoger unas cuantas y volver corriendo a las cajas para llenarlas.

Para hacerlo más emocionante, hay una serie de reglas:

  • Cada caja tiene una capacidad distinta. En concreto, en la primera caja entra una bola, en la segunda caja entran dos bolas, y así sucesivamente hasta llegar a la caja e-nésima en la que entran N bolas.
  • En cada paseo, el concursante puede meter bolas en todas las cajas que quiera. Eso sí, el número de ellas que mete en cada caja debe ser el mismo cada vez. Por ejemplo, si en un paseo decide meter 3 bolas en una caja, tendrá que meter 3 bolas en todas las demás cajas que elija. Eso hace que, evidentemente, si en una caja entran ya menos de 3 bolas, no podrá seleccionarla (pues no metería 3, sino menos).
  • Del tanque puede sacar cualquier número de bolas (podemos asumir que es capaz de cargar con ellas, por muy grande que sea el número). Eso sí, todas las bolas que coja tiene que meterlas en las cajas; no puede dejarse bolas sin usar.

Por ejemplo, si hay cuatro cajas, las capacidades iniciales son 1, 2, 3 y 4. El concursante podría poner 2 bolas en las tres últimas cajas, por lo que éstas quedarían con 0, 2, 2 y 2 bolas. En el segundo viaje podría añadir una bola en la primera, tercera y última caja, con lo que tendríamos 1, 2, 3 y 3 bolas. El tercer y último viaje, con una única bola, terminaría de llenar la caja que faltaba.

Dado un número N de cajas inicial, ¿cuántos paseos como mínimo tendrá que hacer el concursante?

Entrada

La entrada estará formada por distintos casos de prueba cada uno en una línea. En cada una habrá un único entero N (1 ≤ N ≤ 109).

Salida

Por cada caso de prueba se escribirá, en una línea independiente, el número mínimo de paseos necesarios para llenar todas las cajas cumpliendo las normas del concurso.

Entrada de ejemplo

3
4

Salida de ejemplo

2
3