# 327 : 運命の部屋

3つの部屋が自動ドアをへだてて互いにつながっている。

![p327\_rooms\_of\_doom.gif](https://projecteuler.net/project/images/p327_rooms_of_doom.gif)

各ドアはセキュリティカードによって操作される。いったん部屋に入るとドアは自動で閉まり、セキュリティカードは二度と使えなくなる。スタート地点にあるカード発行機からカードを無制限に出すことができるが, （スタートの部屋を含む）各部屋には検知機があり、もし 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 \leq C \leq 4$$に対し$$\sum M(C,6)=146$$である。

$$3 \leq C \leq 10$$に対し$$\sum M(C,10)=10382$$である。

$$3 \leq C \leq 40$$に対し$$\sum M(C,30)$$を求めよ。
