Problem
O arranha-céu tem n andares. Sabe-se que se você deixar cair uma bola de vidro do andar número p e a bola quebrar, se você deixar cair uma bola do andar número p+1, ela também quebrará . Sabe-se também que, ao ser lançada do último andar, a bola sempre quebra.
Você deseja definir o número mínimo de andares que fará com que a bola quebre ao cair. Para experimentos, você tem duas bolas. Você pode dividir todos eles, mas deve ter certeza absoluta desse número no resultado final.
Determine quantos lances são suficientes para resolver este problema.
Entrada
O programa recebe como entrada o número de andares do arranha-céu n.
Saída
É necessário imprimir o menor número de lances, no qual sempre é possível resolver o problema.
Nota
Comente o primeiro exemplo. Você precisa jogar a bola do 2º andar. Se quebrar, lançaremos a segunda bola do 1º andar e, se não quebrar, lançaremos a bola do 3º andar.
Dicas
1. O que você deve fazer se houver apenas uma bola?
2. Sejam duas bolas e lançamos uma bola do andar número k. Como agiremos se a bola quebrar ou não?
3. Seja
f(n) o número mínimo de lançamentos necessários para determinar o andar desejado se o arranha-céu tiver
n andares. Expresse
f(n) em termos de valores
f(a) para valores
a menores.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until