OMC181(C)

ユーザー解説 by Hola

東西の道をそれぞれ北から北道，中央道，南道とする．
南北の道が $n+1$ 本あるとき，小野田と芹沢が東西の道のうち最後に通るのがそれぞれ北道と南道である場合の数を $a_n$ ，北道と中央道である場合の数を $b_n$ ，中央道と南道である場合の数を $c_n$ とする．
対称性より $b_n=c_n$ である．
小野田と芹沢は同じ南北の道を通れないので， $a_{n+1}=a_n+b_n+c_n=a_n+2b_n$ $b_{n+1}=a_n+b_n$ $a_1=1，b_1=1$ 求めたいのは $a_9+2b_9$ なのであとは頑張りましょう．