No.320 On a Sleepless Night
タグ : / 解いたユーザー数 147
作問者 :
threepipes_s
Problem Statement
Yuki-chan, who cannot sleep, decided to count sheep until she gets sleepy.
Since counting normally would be boring, she counted with the number of sheep increasing like the Fibonacci sequence.
That is, the number of sheep at the $i$-th step is represented by $a_i$, where
$a_1=1$, $a_2=1$, $a_{i}=a_{i-1}+a_{i-2}$
.
However, because Yuki-chan was sleepy, she miscounted several times.
Specifically, she several times made the mistake of counting one too few, as in $a_i=a_{i-1}+a_{i-2}-1$ $(i\ge3)$.※
When Yuki-chan woke up in the morning, she remembered that she had counted sheep up to the $N$-th step and that the last count was $M$ sheep, but she cannot remember how many times she made a mistake.
You decided to calculate on her behalf how many times Yuki-chan miscounted.
Yuki-chan would be sad if told of many mistakes, so if multiple values are possible, tell her the smallest among them.
If $M$ cannot be obtained under the above conditions, output $-1$.
※She never counts two or more too few in a single calculation.
※She never makes a mistake on $a_1$ or $a_2$.
Input
N M
$3\le N\le 80$
$1\le M\le 10^{18}$
Note that $M$ may not fit in a 32-bit integer.
Output
Output the number of times Yuki-chan miscounted on one line.
If multiple values are possible, output the smallest one.
If $M$ cannot be obtained under the conditions in the problem statement, output $-1$.
Print a newline at the end.
Sample
Sample 1
Input
7 9
Output
2
If she makes mistakes at the 4th and 7th steps, the sequence becomes
$1, 1, 2, 2, 4, 6, 9$
.
Sample 2
Input
5 5
Output
0
Yuki-chan did not miscount even once.
Sample 3
Input
67 17308070087783
Output
26
Note that $M$ can be large.
Sample 4
Input
5 6
Output
-1
It seems she remembered the wrong $M$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。