Puzzle #28. Цепь

🎲 Вам необходимо собрать цепь из остатков, цена разрезания и сварки одного звена цепи стоит 100 руб. Вам необходимо оптимальным способов собрать цепь в каждом из случаев.

• 1 случай: даны 7 отдельных звеньев цепи, вам нужно сделать из них одну цепь.
• 2 случай: даны 5 обрывков цепи, по 3 звена в каждом из них (aaa bbb ccc ddd eee). Необходимо собрать полную цепь.

Разбор:

1 случай: самый очевидный и неоптимальный способ - разрез и сварка каждого из первых 6ти звеньев. Но это обойдется вам в 600 рублей.

Однако, если подумать, то можно разрезать 2е звено и сковать 1е и 3е звено, таким же образом сковать 4е и 6е 5м звеном. 

Получим 2 цепочки:

• 1 - 2 - 3
• 4 - 5 - 6

В конце разрезаем 7е звено и делаем полную цепь. Вся операция обойдется в 300 рублей.

2 случай: на первый взгляд, цепь можно получить минимум за 4 разреза и сковки. Но можно сделать оптимальнее, если разрезать каждое звено первого обрывка. Получаем только 4 обрывка цепи и 3 звена для сцепки.

bbb - a - ccc - a - ddd - a - eee

Это обойдется в 300 рублей.