*[[Problem 327:http://projecteuler.net/problem=327]] 「運命の部屋」 [#d5399926]
3つの部屋が自動ドアをへだてて互いにつながっている.
#ref(http://projecteuler.net/project/images/p327_rooms_of_doom.gif,center,nolink);
各ドアはセキュリティカードによって操作される. いったん部屋に入ると, ドアは自動で閉まり, セキュリティカードは二度と使えなくなる. スタート地点にあるカード発行機からカードを無制限に出すことができるが, （スタートの部屋を含む）各部屋には検知機があり, もし 3 枚を超える枚数のカードを持っていたり, 所有されていないカードが床にあることが検知されると, 全てのドアは永久的にロックされる. しかし, 各部屋には保管ボックスがあり, 後で使うために任意の枚数のセキュリティカードを安全に蓄えておくことができる.
単純に部屋を一つずつ通り抜けようとすると, 部屋 3 に入った時点で 3 枚のカードを使い切ってしまい, 永久に部屋に閉じこめられてしまうことになるだろう.
しかし, 保管ボックスを利用すると, 脱出は可能である. 例えば, 1 枚目のカードを用いて部屋 1 に入り, 保管ボックスにカードを 1 枚置き, 3 枚目のカードを使って部屋を出てスタートに戻る. そしてさらに 3 枚のカードをカード発行機から出せば, 1 枚を使って部屋 1 に入り, 先ほどボックスに置いたカードを回収する. これで再びカードは 3 枚になるので残りの 3 つのドアを通り抜けることができる. このやり方だと, 計 6 枚のセキュリティカードを使って 3 つの部屋を通り抜けることができる.
最大 3 枚のカードを持てるとき, 計 123 枚のセキュリティカードを用いれば 6 つの部屋を通り抜けることが可能である.
一度に持つことができるカードの最大の枚数を C とする.
通り抜ける部屋の数を R とする.
一度に持てるカードの枚数が最大 C 枚のときに R 個の部屋を通り抜けるのにカード発行機から出すべきカードの最小数を M(C,R) とする.
たとえば, M(3,6)=123 と M(4,6)=23 である.
また, 3≦C≦4 に対し, ΣM(C,6)=146 である.
3≦C≦10 に対し, ΣM(C,10)=10382 である.
3≦C≦40 に対し, ΣM(C,30) を求めよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
