Gefährliche Experimente
Du hast ein Gebäude mit
n Stockwerken und k identischen Flaschen zur Verfügung. Jede dieser Flaschen kann von einer beliebigen Etage des Gebäudes fallen gelassen werden und zerbricht, sobald sie von oder oberhalb einer bestimmten Etage abgeworfen wird.Deine Aufgabe ist es, mit den gegebenen Flaschen die minimale Anzahl an Versuchen zu ermitteln, die notwendig ist, um die niedrigste Etage zu finden, von der aus eine Flasche beim Fallenlassen zerbricht.
Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen
n (100 ≤ n ≤ 500) und k (1 ≤ k ≤ 30), die die Anzahl der Stockwerke im Gebäude bzw. die Anzahl der Flaschen angeben.Ausgabe
Gib eine einzige ganze Zahl aus, die angibt, wie viele Versuche mindestens nötig sind, um die gesuchte Etage mithilfe der Flaschen zu bestimmen.
Beispiele
Eingabe | Ausgabe |
100 2 | 14 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB