Problem
Le gratte-ciel a n étages. Il est connu que si vous faites tomber une boule de verre depuis l'étage numéro p et que la balle se casse, alors si vous faites tomber une boule de verre depuis l'étage numéro p+1, elle se cassera également . Il est également connu que lorsqu'elle est lancée du dernier étage, la balle casse toujours.
Vous souhaitez définir le nombre d'étages minimum qui fera casser la balle lorsqu'elle tombe. Pour les expériences, vous avez deux balles. Vous pouvez tous les diviser, mais vous devez être absolument certain de ce nombre dans le résultat final.
Déterminez combien de lancers suffisent pour résoudre ce problème.
Entrée
Le programme reçoit en entrée le nombre d'étages du gratte-ciel n.
Sortie
Il est nécessaire d'imprimer le plus petit nombre de lancers, auquel il est toujours possible de résoudre le problème.
Remarque
Commentez le premier exemple. Vous devez lancer la balle du 2ème étage. Si elle casse, nous lancerons la deuxième balle du 1er étage, et si elle ne casse pas, nous lancerons la balle du 3ème étage.
Conseils
1. Que faire s'il n'y a qu'une balle ?
2. Soit deux balles et nous avons lancé une balle depuis l'étage numéro k. Comment allons-nous agir selon que la balle casse ou non ?
3. Soit
f(n) le nombre minimum de lancers requis pour déterminer l'étage souhaité si le gratte-ciel avait
n étages. Exprimez
f(n) en termes de valeurs
f(a) pour des valeurs
a plus petites.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until