2/15 PKU

1778 All Discs Considered

2枚のDVDにインストールすべきソフトウェアが入っているが、依存関係があり、ある部分をインストールする前に他の部分をインストールしなければならない、などが定まっている。DVDドライブが空の状態から始めて、すべての部分をインストールし、またDVDドライブを空の状態にするまでにかかるDVDの入れ替え回数の最小値を求めよ。

どう考えてもDVDを(1→)2→1→2→…と入れ替えていく方法しかないので、2通り試す。

1618 Decorations

N種類のビーズで長さLの飾りを作る。飾りをある長さに切り出した時、それは定められたM種類のもののどれかになっていないといけない。何通りの飾りができるか。

DP。Lが小さすぎるときは0を返さないといけないらしい