操作 $4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow \cdots$ と続けることを考えます． ここで，操作を合計 $S$ 回行ったとします． 便利のため，$S$ は偶数であるとします．

任意の $i$ ($0 \leq i \leq S$) について，$i$ 回目の操作後に操作 $1$ か操作 $2$ を行うことを考えます． すると，以下のことがわかります．

• $i$ が偶数の場合：操作 $1$ を $1$ 回行うたびに，最終的な $x$ の値が $fib(S-i)$ 増える．
• $i$ が奇数の場合：操作 $2$ を $1$ 回行うたびに，最終的な $x$ の値が $fib(S-i)$ 増える．

ただしここで，$fib(n)$ はフィボナッチ数($fib(0)=1,fib(1)=1,fib(n)=fib(n-1)+fib(n-2)$ for $2 \leq n$)を表します．

各 $i$ について，高々 $1$ 回だけ操作 $1$ or $2$ を行うことを考えてみます． この場合，$S$ の値としては，$fib(S) \leq 10^{18}$ となる最大の $S$ を選べばよいです．それ以上大きい $S$ は無駄であるためです． 実際に計算すると $S=86$ を選べばよいとわかります．

あとは，$fib(S-i)$ の和で $N$ を作る問題を解けばよいです． これは，$i$ の小さい方から，操作が行えるなら行う貪欲をすればよいです． この時，$i$ と $i+1$ 両方で操作することはありません． なぜなら，その場合は $i-1$ で操作すればいいからです． よって，操作 $1$ or $2$ の回数は $S/2+1=44$ で抑えられます． （なお，実際には最大で $43$ 回です）

よって，全体の操作回数が $86+44=130$ 回で抑えられ，この問題が解けます．