Дискретная математика

[sover]

Есть набор (1,5)(1,6)(5,5)(2,4)(2,4) не может быть размещён в строке.Однако если добавить (2,5), то полученный набор можно можно разложить в следующей строке6,1)(1,5)(5,5)(5,2)(2,4)(4, 2).

Задача состоит в том , чтобы написать программу, которая для данного набора домино найдёт дополнительный набор, чтобы строка могла быть размещена с обоими объединёнными наборами блоков.
Сумма чисел дополнительного набора должна быть минимальна.
Однако если вместо части (2,5) с суммой 7, добавить две части (1,2) с полной суммой 6 то можно разложить так:
(5,5)(5,1)(1,2)(2,4)(4,2)(2,1)(1,6) <-вот это и надо получить.

Чёт я не очень представляю как её делать, подскажите алгоритм, или в какую сторону копать.

З.Ы. язык си++ =)

[sover]

Помогите хотя бы с алгоритмом, или где поискать.

[KobolD]

А почему у тебя в колоде повторяющиеся доминоошки есть (2,4)?
Видимо надо создать функцию которая принимает два параметра: первый текущая "доминошка" и массив не использованных доминошек, функция ищет в массиве след доминошку и рекурсивно себя вызывает. По окончанию работы функции должно получиться три параметра: значение первого числа в последовательности, значение последнего числа последовательности, массив не использованных доминошек.
В основной программе запускаеш вышеописаную функцию с первой доминошкой и массивом из всех остальных, потом снова запускаешь ее же с параметрами: первой доминошкой из неиспользованной последовательности и массивом неиспользованных доминошек без первой.
В результате у тебя должно получиться четыре числа: начало и конец первой последовательности и начало и конец второй последовательности. Из них надо найти минимальную сумму - это и будет ответ.

[sover]

Сообщение от KobolD

А почему у тебя в колоде повторяющиеся доминоошки есть (2,4)?

так в задании описано что могут быть и повторяющиеся

[sover]

KobolD алгоритм который ты предложил не подходит, если делать так как ты говоришь то получится примерно следующее (6,5) (2,2) между ними можно поставить (2,5).

Однако если вместо части (2,5) с суммой 7, добавить две части (1,2) с полной суммой 6 то можно разложить так:
(5,5)(5,1)(1,2)(2,4)(4,2)(2,1)(1,6) <-вот это и надо получить.
вот в этом и заключается проблема, в задании говорится что сумма должа быть как можно меньше.

[sover]

неужели никто с подобным не сталкивался ?

[Biggs]

Так у тебя же есть алгоритм-если есть две домино со значениями (A,B)-(C,D) и A,B,C,D не совпадают
то надо добавить (B,1),(1,C) или (B,C) при этом B,C должны быть минимумами в своих костяшках
Естественно надо посчитать, что больше и добавить меньшее