Олимпиадные задачи по программированию — очень интересное явление. Чего только не придумывают организаторы соревнований, чтобы заставить студентов и школьников пошевелить мозгами! Задачи встречаются самые разные: забавные и скучные, полезные и не имеющие явного практического применения.

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

Сегодня я приведу решение задачи «Чайнворд», предлагавшейся на 15-й Всероссийской олимпиаде по информатике в 2003 г. Автор задачи Михаил Климов.

Условие

Журналисты газеты The Run Times к каждому номеру готовят чайнворд. Чайнворд — это последовательность клеток, куда читатель вписывает угаданные слова. Каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква у них общая, т.е. записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова «set», «too» и «olymp» следующим образом: «setoolymp».

Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга «soly», который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.

Для экономии места в газете журналисты стремятся придумать чайнворд минимальной длины.

Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.

Входные данные

В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N — количество слов, которые можно использовать при составлении чайнворда (1

Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов.

Выходные данные

В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них.

Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ — знак вопроса.

Примеры

chain.in

soly

4

set

olymp

lye

too

chain.out

set

too

olymp

chain.in

solve

4

set

owe

evil

too

chain.out

?

Решение

В этой статье я предлагаю свой собственный алгоритм решения.

Сначала считаем все слова в массив. Теперь нам необходимо создать массив расстояний от буквы до буквы (двумерный) t[?a?..?z?, ?a?..?z?], где каждый элемент содержит следующие данные:

  • длина пути от буквы до буквы,
  • используемое слово (если в пути одно слово),
  • буква, через которую осуществляется переход слов (если в пути более одного слова).

Прежде всего заполним массив минимальными длинами слов. То есть если в списке есть слова too и to, то t[?t?, ?o?].num = 2.

Теперь необходимо найти переходы с участием нескольких слов. Для этого удобно воспользоваться алгоритмом Флойда. Примерно так должен выглядеть этот кусок кода:

for c1 := 'a' to 'z' do


for c2 := 'a' to 'z' do

for c3 := 'a' to 'z' do

if (t[c2, c3].num > t[c2, c1].num + t[c1, c3].num-1)

then

begin

t[c2, c3].num := t[c2, c1].num + t[c1, c3].num-1;

t[c2, c3].aft := c1;

t[c2, c3].add := 0;

end;

Здесь t.num — количество букв на пути, t.aft показывает, через какую букву проходит путь, когда он идет по цепочке слов, и t.add — через какое слово (в случае если идет по одному слову). Важно, что при суммировании длин двух переходов (от c2 до c1 и от c1 до c3) сумма уменьшается на 1 — буква c1 накладывается.

Теперь у нас имеется список наименьших расстояний, и по нему мы можем восстановить кратчайшую последовательность слов.

Кроме этого нам понадобятся две функции, каждая из которых создает массив, где для каждого слова хранится количество букв, встречающихся в образце начиная с позиции k. То есть допустим, что мы уже составили последовательность, в которой есть k первых букв образца, и нам надо определить, сколько последующих букв образца содержит каждое слово. Например, для образца «soly» уже составлена последовательность для двух первых букв (k = 2). Тогда для слова «olymp» функция должна вернуть значение 2 — в этом слове встречаются буквы «l» и «y». Различие функций состоит в том, что одна из них должна считать количество букв, начиная с первой буквы слова, а другая — со второй. Оба эти массива нам пригодятся впоследствии.

Теперь, собственно, подготовка окончена и начинается решение.

Для решения нам необходим двумерный массив go[1..250, ?a?..?z?]. Каждый его элемент хранит следующую информацию:

  • go[i, c].now - количество букв в строке, содержащей i первых букв образца и заканчивающейся на c;
  • go[k, c].prev - количество букв образца в строке до добавления текущего слова;
  • go[k, c].cpr - последний символ перед добавлением текущего слова;
  • go[k, c].pw - номер слова, которое мы добавили;
  • go[k, c].beetw - флаг, показывающий, использовали ли мы в пути от предыдущего состояния до добавления слова, содержащего буквы образца, другие слова. Вместо него можно ставить особую метку в go.cpr - символ не из множества 'a'..'z'.

Начнем заполнение этого массива.

Прогоним процедуру генерации массива, в котором содержится количество букв образца в слове, включая первую букву слова, с аргументом 0 — в последовательности еще нет ни одной буквы образца (пусть этот массив называется inw[j], где j — номер слова). Теперь организуем цикл (j) по всем словам и внутри него цикл (k) от 1 до inw[j]. Пусть c — последняя буква текущего слова. Если длина слова меньше go[k, c].now (сначала заполним все go.now бесконечностью), то запишем в go[k, c]:

now - длина слова,

prev = 0 - нет предыдущего слова,

beetw или cpr - установим флаг цепочки в false (т.е. нет предшествующей цепочки),

pw = j - номер слова.

Теперь основной этап решения.

Заведем цикл (i) от 1 до количества букв в образце — 1. На каждом шаге формируем функциями два массива вхождений букв образца для каждого слова, считая, что i букв образца уже совпали. Пробегаем циклом (c) по всем буквам, на которые оканчивается текущая строка.

Следующие действия выполняем, только если существует строка, содержащая i символов образца и оканчивающаяся на c. Организовываем еще один внутренний цикл по словам. Если первая буква текущего слова равна c, т.е. слово начинается с той буквы, которой оканчивается текущая последовательность, то организовываем цикл (k) от 1 до количества букв образца, встречающихся в слове j начиная со второй буквы.

В этом цикле проверяем — если последовательность, содержащая i+k букв образца и оканчивающаяся последней буквой слова, не существует или длиннее, чем текущая последовательность go[i, c].num + длина текущего слова (j)-1, то заменяем ее данные на следующие: now = go[i, c].now + length(w[j])-1, prev = i, beetw или cpr = false, pw = j.

Заканчиваем цикл по k и условие совпадения первой буквы слова с последней буквой текущей последовательности (c). Теперь напишем кусок кода для случая, когда первая буква текущего слова и последняя буква последовательности не совпадают.

Организуем цикл (k) от 1 до количества букв образца, содержащихся в слове j начиная с первой буквы. Если последовательность, содержащая k+i первых букв образца и заканчивающаяся на последнюю букву слова, не определена или ее длина превышает go[i, c] + (длина текущего слова-1) + (расстояние от последней буквы текущей последовательности (с) до первой буквы слова — 1), то ставим ей в соответствие новые параметры: num = go[i, c] + t[c, w[j, h]]-1 + h-1, где h — длина слова, w — массив слов; prev = i; pw = j; cpr = c и beetw = true — содержит перед собой цепочку, которая начинается с буквы c и оканчивается первой буквой слова.

После работы этих циклов проверяем наличие ответа. Организовываем цикл по c от ?a? до ?z? и находим минимальное значение go[q, c].now (сохраним c для минимального значения как cbest), где q — длина заданной последовательности. Если минимум равен бесконечности, значит, не существует ни одного чайнворда из заданных слов, содержащего необходимую последовательность. Выводим «?» и выходим из программы.

Если же ответ существует, то его вывод также требует от нас определенных усилий. Мы знаем cbest и с его помощью восстановим лучшую последовательность. Для этого организуем цикл repeat until (сначала j равно длине данной последовательности, pc = cbest) и будем записывать в массив (por) номера слов go[pj, pc].pw и, в случае наличия флага beetw, также устанавливать флаг. После этого pc1 := go[pj, pc].cpr, pj := go[pj, pc].prev, pc := pc1 — переходим к предыдущему слову, содержащему буквы из данной последовательности.

Массив por необходимо перевернуть — он содержит слова в обратном порядке. Затем начинаем выводить слова. В случае, если установлен флаг, непосредственно перед словом необходимо вывести цепочку, соединяющую предыдущее слово с текущим. Для этого воспользуемся обратным рекурсивным обходом дерева, который восстановит всю цепочку в правильном порядке. Текст этой процедуры будет выглядеть примерно так:

procedure addlist(a, b : char);
begin
if t[a, b].add = 0 then begin
addlist(a, t[a, b].aft);
addlist(t[a, b].aft, b);
end else writeln(w[t[a, b].add]);
end;

Сначала в процедуру addlist в качестве a и b передаются последняя буква предыдущего слова и первая буква текущего соответственно.

Общая максимальная сложность алгоритма получается O(KхHхNхL), где K — количество букв в образце (250), H — мощность алфавита (26), N — количество слов (1000) и L — максимальная длина слова (10). В самом худшем случае (практически нереально) получаем порядка 65 млн. операций, что вполне приемлемо для современных компьютеров.

Остальные варианты решений приведены на диске. Они реализованы в редакторе FreePascal и могут быть проверены в любой среде, поддерживающей Паскаль.

2600