天下一プログラマーコンテスト2012 決勝

A - ぶんたん


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB


問題文

フィボナッチ数列は、以下のような漸化式で表される数列 F_0,\ F_1,\ F_2,\ …\ (=0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ …) であり、フィボナッチ数はこの数列に現れる数 F_i\ (i \geq 0) です。

  • F_{0} = 0
  • F_{1} = 1
  • F_{i+2} = F_{i} + F_{i+1} (i \geq 0)

ある正整数 n をいくつかのフィボナッチ数の和として表すことを考えます。
このとき、和が正整数 n となるフィボナッチ数の個数として考えられる最小の値を答えなさい。
ただし、同じフィボナッチ数を複数回用いることもできるものとし、複数回用いた場合はそれぞれ別々に数えるものとします。


入力

入力は以下の形式で標準入力から与えられる。
n
  • 正整数 n (1 \leq n \leq 10^{10}) が 1 行で与えられる。

部分点

与えられる数が小さい入力 (1 \leq N \leq 10^5) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

和が正整数 n となるフィボナッチ数の個数として考えられる最小の値を 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

10

出力例 1

2
    10 は最小で 5 ,\ 52 個のフィボナッチ数の和で表すことができます。

入力例 2

11

出力例 2

2
    11 は最小で 3 ,\ 82 個のフィボナッチ数の和で表すことができます。

入力例 3

10000000000

出力例 3

16

Submit提出する