Запрещённые слова

Гений объясняет

Последовательность с наименьшим штрафом есть повторение некоторого слова, которое можно получить из исходных и некоторых других (если их нет в исходных). Потом мы расширяем все слова до нужной длинны (см вызов функции nok) и сравниваем их штрафы (их уже нужно считать самим). Ну и выбрав слово с наименьшим штрафом повторяем его n раз, и ищем в нем подстроку с минимальным штрафом. Она и есть ответ.

Формулировка задачи

В трёхбуквенном алфавите WIN требуется написать слово Best заданной длины М, минимизируя штраф за вхождение запрещенных слов в написанное слово. Задан список запрещенных слов длины lsw и штраф за запрещенные слова.

Длина выходного слова ограничена: М <= 100.

Длина списка - lsw ограничена, lsw <= 50.

Максимальная длина запрещенного слова - lw ограничена, lw <= 6.

Слова в списке запрещенных слов следуют в порядке возрастания длины слова.

Первые три элемента списка - штрафы за буквы алфавита.

Входной файл

Первая строка – M.

Вторая строка - lsw.

Последующие lsw строк содержат через пробел запрещенное слово и штраф за это слово.

Выходной файл

Слово Best и штраф за него.

Пример входного файла:

8
8
I 10
N 30
W 10
WI 1
WW 10
II 11
WIW 3
IWI 2

Выходной файл:

IWIWIWIW
98

Разработка

Необходимые методы:

1. Берёт на вход строку и разбирает её на слова штрафов

   Вход: string "WINI", слова штрафов - array of strings [WI, I, INI, NI].

   ВЫХОД:[I, I, WI, NI, INI]

2. Берёт слова штрафов и отдаёт сумму всего штрафа

   ВХОД:[I, I, WI, NI, INI]

   ВЫХОД: какой-то int

3. Парсинг файла.

4. Ищет оптимальное слово. (Задача о заполнении рюкзака).