Module: ダイナミックプログラミング。基本

Problem

昔々、子供の頃、私たちは皆「Pebbles」というゲームを楽しんだことがありました。または、誰かがそれを呼んだ「5 つの小石」。 ゲームには、路上で簡単に見つかる普通の小石が必要でした。どこでもプレイすることが可能でした。 ゲームの最初のステップは次のとおりでした。 5 つの小石はすべて、目の前の地面に投げられます。そのうちの1人が選ばれました。これは手球です。この小石は空中に投げられ、それが飛んでいる間、地面に残っている小石の1つを拾い、同じ手で飛んでいる小石を捕まえる時間が必要です。拾った小石は脇に置き、残りの小石すべてに対してこの操作を繰り返します。
次のステップでは、拾う小石の数が増えます。最後のステップは試験で、集めた小石をすべて空中に投げて手の甲でキャッチし、もう一度投げて開いた手のひらでキャッチする必要がありました。最終的に小石が何個残ったか、それだけ多くのポイントを獲得できます。順番は次のプレイヤーに移り、次のプレイヤーもすべての手順を繰り返します。その後、ゲームの新しいラウンドが開始されました。 すべてのラウンドで最も多くのポイントを獲得した人が勝者となります。
多くの人があらゆる方法でゲームを難しくし
ました。 彼らが地面に無数の小石を置いているとしましょう。ラウンドの終わりに、すべての小石を手のひらでつかむ必要はありませんが、合計ポイントが 1 つ、または 2 倍、または 3 倍に増加するのに十分な量です。ゲーム開始前に全員がすでに 1 ポイントを持っています。 N ポイントをより早く獲得した人が勝者となります。
すべてのプレイヤーが十分なプレイ経験を持ち、常に必要な石の数を持って試験に到達すると仮定します（必要なポイント数を 1、2、または 3 倍増やすことができます）。

1  から指定されたポイント数 N を取得するためにプレイする必要がある最小ラウンド数を決定します。

入力

プログラムは、10⁶ を超えない単一の数値を入力として受け取ります。

出力

数値を 1 つ出力する必要があります。これは、探している操作の最小数です。

 

 

例

<頭> <本体>

 

#	入力	出力
1	1	0
2	5	3
3	32718	17