Problem
Il grattacielo ha n piani. È noto che se lasci cadere una palla di vetro dal piano numero p e la palla si rompe, allora se lasci cadere una palla dal piano numero p+1, si romperà anch'essa . È anche noto che quando viene lanciata dall'ultimo piano, la palla si rompe sempre.
Vuoi definire il numero minimo di piani che causerà la rottura della palla quando cade. Per gli esperimenti, hai due palle. Puoi dividerli tutti, ma devi essere assolutamente certo di quel numero nel risultato finale.
Determina quanti lanci sono sufficienti per risolvere questo problema.
Input
Il programma riceve in input il numero di piani del grattacielo n.
Uscita
È necessario stampare il minor numero di lanci, al quale è sempre possibile risolvere il problema.
Nota
Commenta il primo esempio. Devi lanciare la palla dal 2 ° piano. Se si rompe, lanceremo la seconda palla dal 1° piano, e se non si rompe, lanceremo la palla dal 3° piano.
Suggerimenti
1. Cosa dovresti fare se c'è solo una palla?
2. Lascia che ci siano due palle e abbiamo lanciato una palla dal numero del piano k. Come agiremo a seconda che la palla si rompa o meno?
3. Sia
f(n) il numero minimo di lanci richiesti per determinare il piano desiderato se il grattacielo avesse
n piani. Esprimi
f(n) in termini di valori
f(a) per valori
a più piccoli.
Esempi
| # |
Input |
Uscita |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until