Euler.net – 327- Rooms of Doom 解き方

3つの部屋は1列で自動ドアによって互いに繋がっています。
各ドアは、セキュリティ・カードにより操作されます。部屋に入るとドアが自動的に閉じ、そのセキュリティカードを再度使用することはできません。開始時、カードの数に制限を分配しますが、各部屋(出発室にも)には、スキャナが含まれており、最大3つのカードしかを持てる。各部屋には、セキュリティカードの任意の数を格納することができるボックスがあります。

単に一度部屋1を通過しようとした場合は、部屋3に入ると、あなたはすべてのカードを3枚使用しているだろうと永遠にその部屋に閉じ込められたことになります。

ただし、収納ボックスを利用する場合は、エスケープが可能です。たとえば、あなたは、あなたの最初のカードを使用して、部屋1を入力収納ボックス内の1つのカードを配置し、出発室に戻ってまた3枚のカードを得る。あなたは部屋1に入って、ボックスにあるカード1枚を得る。これで、再びカードを3枚持っていると、残りの3つのドアを通って移動することができるようになります。この方法では、合計で6セキュリティカードを使用して、すべての3つの部屋を通って移動することができます。

これは、3枚が持てるカードを最大値だとすると、123枚のカードを使ったら、6室を通って移動することが可能です。

Cは、任意の時点で実施することができるカードの最大数とします。

Rが通過する部屋の数とします。

M(C、R)は、いつでもCカードの最大値まで運ぶのR部屋を通過する必要なカードの最小数とします。

例えば、M(3,6)=123、M(4,6)= 23
そして、ΣM(C、6)= 3≤C≤4のための146。

ΣM(C、10)= 3≤C≤10のための10382。

3≤C≤40のためΣM(C、30)は?

こんな問題です。

この問題はDP(Dynamic Programming)問題です。

簡単に例でM(4,6)から考えます。説明をため出発室は部屋0、1番目の部屋は部屋1などで言います。もし部屋1のボックスに部屋2〜最後の部屋まで行けるカードがあったら私たちはまた部屋0にもどらなくてもいいです。部屋2〜最後の部屋まで行くため必要なカードの数はM(4,6-1)です。(部屋1を無視するので部屋の数が1減る)

M(4,6) = M(4,5) + (カードM(4,5)枚を部屋1に移すために必要なカードの数) + 1 です。(移す事が終わった後で最後の1は部屋0から部屋1まで行くため)

(カードM(4,5)枚を部屋1に移すために必要なカードの数) は 簡単に計算ができます。

もしカードを最大N枚を持てるとすると、1回にカードはN-2枚移す事ができます。(2個は部屋に移動するため使うので)また実はカードをM(4,5)枚じゃなくてM(4,5)-(c-1)枚だけ移ったらいいです。(M(4,5)-(3)] / [2])回動くとカードは全部移れます。でも回数は自然数だけなのでceilを使います。ex) 3.7回 → 4回

M(4,6) = M(4,6) + 1 + 2*ceil([M(4,5)-(3)] / [2]) です。

M(c, r) = M(c,r-1) + 1  + 2*ceil([M(c,r-1)] – (c-1)] / [c-2]) です。

もし c > r なら M(c,r) == r+1 です。

import math

def m(c, r):
    if r < c:
        return r+1
    m_r_1 = m(c, r-1)
    return m_r_1 + 1 + 2*math.ceil((m_r_1-c+1)/(c-2))

print (sum(m(c, 30) for c in range (3, 40+1)))

終わりです。

 

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중