Problem
El rascacielos tiene n pisos. Se sabe que si dejas caer una bola de cristal desde el piso número p y la bola se rompe, entonces si dejas caer una bola desde el piso número p+1, también se romperá. . También se sabe que cuando se lanza desde el último piso, la pelota siempre se rompe.
Desea definir el número mínimo de piso que hará que la pelota se rompa cuando caiga. Para los experimentos, tienes dos bolas. Puede dividirlos todos, pero debe estar absolutamente seguro de ese número en el resultado final.
Determina cuántos lanzamientos son suficientes para resolver este problema.
Entrada
El programa recibe como entrada el número de pisos del rascacielos n.
Salida
Se requiere imprimir el menor número de lanzamientos, en el que siempre es posible resolver el problema.
Nota
Comenta el primer ejemplo. Necesitas lanzar la pelota desde el segundo piso. Si se rompe, tiraremos la segunda pelota desde el 1er piso, y si no se rompe, arrojaremos la pelota desde el 3er piso.
Consejos
1. ¿Qué debes hacer si solo hay una bola?
2. Sean dos bolas y hemos lanzado una bola desde el piso número k. ¿Cómo actuaremos en función de si la pelota se rompe o no?
3. Sea
f(n) el número mínimo de lanzamientos necesarios para determinar el piso deseado si el rascacielos tuviera
n pisos. Expresar
f(n) en términos de valores
f(a) para valores menores de
a.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until