ｸｲｽﾞ大陸

n段目の棚を開閉する動作を[n]、複数の棚を連続で開閉する動作を[a,b,c,…]と表現すると

<tt>　　　　　　　　　　　　　　　　 1段目の棚の状態を反転：A₁ = [1]
1段目の棚まで全て閉じているとき、2段目の棚の状態を反転：A₂ = [1,2,1]
2段目の棚まで全て閉じているとき、3段目の棚の状態を反転：A₃ = [1,2,1,3,1,2,1]</tt>

(n-1)段目の棚まで全て閉じているとき、n段目の棚の状態を反転する手順をA_nとすると、
A_n = A_n-1 + [n] + A_n-1 と表ることができます。
また、A_nを実行するのにかかる手数は 2ⁿ - 1 手であることも確認できます。

今回の問題では6段目の棚を開ける必要があります。
そのためには5段目の棚だけを開いた状態にする必要があるので、
6段目の棚を開けるまでの手順はA₅ + [6]となります。

しかし、一つ上の棚が開いている状態では、すぐ上の棚が邪魔で箱は取り出せない。
よって、5段目の棚を閉じる動作も行う必要があります。
取り出せるようになるまでの手順は A₅ + [6] + A₄ + [5] 、手数は 31 + 1 + 15 + 1 = 48手。
※一般的に、n番目(n≧2)の棚から箱を取りだすためには、最短 3 × 2ⁿ / 4 手がかかるようです。

<tt>動かし方の図解。□◇：閉じた棚　■◆：開いた棚
　　┌──　　　　　　　　　　　A₅前半　　　　　　　　　　　──┐
□　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□
□　□　◆　■　■　■　◇　□　□　□　◆　■　■　■　◇　□　□
□→□→□→□→◆→■→■→■→■→■→■→■→◇→□→□→□→□┐ 16
□　□　□　□　□　□　□　□　◆　■　■　■　■　■　■　■　■│
□　□　□　□　□　□　□　□　□　□　□　□　□　□　□　□　◆│
□　□　□　□　□　□　□　□　□　□　□　□　□　□　□　□　□│
┌────────────────────────────────┘
│　┌──　　　　　　　　　　　A₅後半　　　　　　　　　──┐ [6]
│　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□
│　□　◆　■　■　■　◇　□　□　□　◆　■　■　■　◇　□　□
└→□→□→□→◆→■→■→■→■→■→■→■→◇→□→□→□→□┐ 32
　　■　■　■　■　■　■　■　◇　□　□　□　□　□　□　□　□│
　　■　■　■　■　■　■　■　■　■　■　■　■　■　■　■　■│
　　□　□　□　□　□　□　□　□　□　□　□　□　□　□　□　◆│
┌────────────────────────────────┘
│　┌──　　　　　　　　　　　A₄　　　　　　　　　　　──┐ [5]
│　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□　◆　■　◇　□
│　□　◆　■　■　■　◇　□　□　□　◆　■　■　■　◇　□　□
└→□→□→□→◆→■→■→■→■→■→■→■→◇→□→□→□→□　 48
　　□　□　□　□　□　□　□　◆　■　■　■　■　■　■　■　■
　　■　■　■　■　■　■　■　■　■　■　■　■　■　■　■　◇
　　■　■　■　■　■　■　■　■　■　■　■　■　■　■　■　■</tt>