Break Rings Break Rings
Challenging
EN ES FR Japanese RU

鍛冶屋が彼のいとこにリングを整理するために選択しろという仕事を与えた。 いとこはまだその仕事のスキルがなく、結果としていくつかの(正直にいうとほとんどの)リングが一緒につながってしまった。 彼はリングを切り離しなるべく多くの数のリングを残そうとあなたに助けを求めている。

すべてのリングには番号が振られていて、あなたはどのリングが繋がっているか知らされている。 この情報はsetの情報として与えられる。それぞれのsetは繋がっているリングを記述している。例えば、{1, 2}は1番目と2番目のリングが繋がっているという意味である。 あなたはもっとも多くの切り離されたリングを得るために、いくつリングを壊さなければいけないか数えなければいけない。 それぞれのリングは1からNまでの範囲の数字で番号が付けられており、Nはリングの数である。

example-rings

上の画像では次の繋がりがわかる[[1,2],[2,3],[3,4],[4,5],[4,6],[6,5]] ここでの最適な解決法は3つのリングを壊し、3つの完全に切り離されたリングを得ることである。 従って結果は3となる。

整数のセットのタプルとして与えられる繋がったリングの情報

壊すべきリングの数の整数

break_rings(({1, 2}, {2, 3}, {3, 4}, {4, 5}, {4, 6}, {6, 5})) == 3

このモデルは特定の状態の何かを最適化することに特化している。その基本的なコンセプトを使って、輸送網を改善するモデルを作ることができるかもしれない。

all(len(s) == 2 for s in rings)
sorted(reduce(set.union, rings)) == list(range(1, max(reduce(set.union, rings)) + 1))

You should be an authorized user in order to see the full description and start solving this mission.