SRM298 Div2 500

問題

フィボナッチ数列のFiが与えられるので、それに対応するインデックスiを計算して返す。
ただし、Fi=1ならばi=2、Fiに対応するiが存在する場合はそのi、Fiに対応するiが存在しない場合(例えばFi=4)はその前後の存在するFi,F{i+1}の値を線形補間して返す。

Fi=4ならば、その前後で存在するのはF[4]=3とF[5]=5なので、i=4+(4-3)/(5-3)=4.5。

考え方

やるだけ。

nが10^8まであるが、フィボナッチ数列はすぐにその程度の大きさになるので、オーバーフローに気を付ける。