問題一覧 > 通常問題

No.320 眠れない夜に

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : threepipes_sthreepipes_s
29 ProblemId : 875 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-12 04:42:36

問題文

眠れないゆきちゃんは、眠くなるまで羊を数えることにしました。
普通に数えてはつまらないので、フィボナッチ数列状に羊が増えることにして数えました。
つまり、$i$番目の羊の数は、
$a_1=1$、$a_2=1$、$a_{i}=a_{i-1}+a_{i-2}$
として$a_i$で表されます。

しかしゆきちゃんは眠かったために、何度か数え間違いをしてしまいました。
具体的には、$a_i=a_{i-1}+a_{i-2}-1$ $(i\ge3)$のように、1少なく数えてしまうというミスを何度かしました。※

朝起きたゆきちゃんは、$N$番目まで羊を数えて最後が$M$匹であることは思い出したのですが、何度間違えたのかが思い出せません。
ゆきちゃんが何度数え間違えたか、あなたはかわりに計算してあげることにしました。

間違いを多く伝えるとゆきちゃんが悲しむので、複数通り考えられる場合はそのうちもっとも小さい数を教えてあげてください。
上記の条件で$M$になることがない場合は$-1$を出力してください。

※一度の計算で2以上少なく数えてしまうことはありません
※$a_1$と$a_2$を間違えることはありません

入力

N M

$3\le N\le 80$
$1\le M\le 10^{18}$
$M$は32bit整数に収まらない場合があるので注意してください。

出力

ゆきちゃんが間違えた回数を一行で出力してください。
複数通り考えられる場合は、もっとも小さい場合の値を出力してください。
問題文の条件で$M$になることがない場合、$-1$を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
7 9
出力
2

4番目と7番目で間違えると、
$1, 1, 2, 2, 4, 6, 9$
という数列になります。

サンプル2
入力
5 5
出力
0

ゆきちゃんは一度も数え間違えませんでした。

サンプル3
入力
67 17308070087783
出力
26

$M$が大きくなる場合もあるので注意してください。

サンプル4
入力
5 6
出力
-1

間違った$M$を思い出してしまったようです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。