A - ぶんたん
解説
/
入力は以下の形式で標準入力から与えられる。
与えられる数が小さい入力 (1 \leq N \leq 10^5) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。
和が正整数 n となるフィボナッチ数の個数として考えられる最小の値を 1 行で出力せよ。
なお、行の終端には改行が必要である。
実行時間制限: 2 sec / メモリ制限: 64 MB
問題文
フィボナッチ数列は、以下のような漸化式で表される数列 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
10
出力例 1
2
-
10 は最小で 5 ,\ 5 の 2 個のフィボナッチ数の和で表すことができます。
入力例 2
11
出力例 2
2
-
11 は最小で 3 ,\ 8 の 2 個のフィボナッチ数の和で表すことができます。
入力例 3
10000000000
出力例 3
16