Problem
In einem Wolkenkratzer von n Etagen. Es ist bekannt, dass, wenn Sie eine Glaskugel aus der p -Etage fallen lassen und die Kugel zerbricht, wenn Sie die p+1 -Etage fallen lassen, sie ebenfalls zerbricht. Es ist auch bekannt, dass der Ball beim Werfen aus dem letzten Stock immer bricht.
Sie möchten die minimale Anzahl des Bodens bestimmen, aus dem die Kugel fällt, wenn sie herunterfällt. Um Experimente durchzuführen, haben Sie zwei Kugeln. Sie können sie alle aufteilen, aber als Ergebnis müssen Sie diese Nummer absolut genau identifizieren.
Bestimmen Sie, wie viele Würfe ausreichen, um diese Aufgabe bewusst zu lösen.
Eingabe
Das Programm erhält die Anzahl der Stockwerke im Wolkenkratzer n.
Ausgabe
Sie müssen die geringste Anzahl von Würfen ausgeben, um das Problem immer zu lösen.
Hinweis
Kommentar zum ersten Beispiel. Wir müssen den Ball aus dem 2. Stock werfen. Wenn er bricht, werfen wir den zweiten Ball aus dem 1. Stock, und wenn er nicht bricht, werfen wir den Ball aus dem 3. Stock.
Hinweise
1. Wie sollte ich vorgehen, wenn es nur einen Ball gäbe?
2. Lassen Sie die Kugeln zwei und wir werfen eine Kugel aus dem Boden der k -Nummer. Wie werden wir handeln, je nachdem, ob die Kugel zerbricht oder nicht?
3. Sei
f(n) die minimale Anzahl von Würfen, für die man die gewünschte Etage bestimmen kann, wenn es in einem Wolkenkratzer
n Etagen gäbe. Drücken Sie
f(n) über die
f(a) -Werte für kleinere
a -Werte aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
4 |
2 |
| 2 |
7 |
3 |
Запрещенные операторы: for; while; until