Олимпиадные задачи по программированию — очень интересное явление. Чего только не придумывают организаторы соревнований, чтобы заставить студентов и школьников пошевелить мозгами! Задачи встречаются самые разные: забавные и скучные, полезные и не имеющие явного практического применения.
Начиная с этого номера мы будем публиковать самые интересные задания из тех, которые ежегодно выполняют участники всероссийских олимпиад по программированию.
Сегодня я приведу решение задачи «Чайнворд», предлагавшейся на 15-й Всероссийской олимпиаде по информатике в 2003 г. Автор задачи Михаил Климов.
Условие
Журналисты газеты The Run Times к каждому номеру готовят чайнворд. Чайнворд — это последовательность клеток, куда читатель вписывает угаданные слова. Каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква у них общая, т.е. записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова «set», «too» и «olymp» следующим образом: «setoolymp».
Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга «soly», который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.
Для экономии места в газете журналисты стремятся придумать чайнворд минимальной длины.
Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.
Входные данные
В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N — количество слов, которые можно использовать при составлении чайнворда (1 Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов. В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них. Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ — знак вопроса. Примеры chain.in Решение В этой статье я предлагаю свой собственный алгоритм решения. Сначала считаем все слова в массив. Теперь нам необходимо создать массив расстояний от буквы до буквы (двумерный) t[?a?..?z?, ?a?..?z?], где каждый элемент содержит следующие данные: Прежде всего заполним массив минимальными длинами слов. То есть если в списке есть слова too и to, то t[?t?, ?o?].num = 2. Теперь необходимо найти переходы с участием нескольких слов. Для этого удобно воспользоваться алгоритмом Флойда. Примерно так должен выглядеть этот кусок кода: Здесь 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?]. Каждый его элемент хранит следующую информацию: Начнем заполнение этого массива. Прогоним процедуру генерации массива, в котором содержится количество букв образца в слове, включая первую букву слова, с аргументом 0 — в последовательности еще нет ни одной буквы образца (пусть этот массив называется inw[j], где j — номер слова). Теперь организуем цикл (j) по всем словам и внутри него цикл (k) от 1 до inw[j]. Пусть c — последняя буква текущего слова. Если длина слова меньше go[k, c].now (сначала заполним все go.now бесконечностью), то запишем в go[k, c]: now - длина слова,
Теперь основной этап решения. Заведем цикл (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 необходимо перевернуть — он содержит слова в обратном порядке. Затем начинаем выводить слова. В случае, если установлен флаг, непосредственно перед словом необходимо вывести цепочку, соединяющую предыдущее слово с текущим. Для этого воспользуемся обратным рекурсивным обходом дерева, который восстановит всю цепочку в правильном порядке. Текст этой процедуры будет выглядеть примерно так: Сначала в процедуру addlist в качестве a и b передаются последняя буква предыдущего слова и первая буква текущего соответственно. Общая максимальная сложность алгоритма получается O(KхHхNхL), где K — количество букв в образце (250), H — мощность алфавита (26), N — количество слов (1000) и L — максимальная длина слова (10). В самом худшем случае (практически нереально) получаем порядка 65 млн. операций, что вполне приемлемо для современных компьютеров. Остальные варианты решений приведены на диске. Они реализованы в редакторе FreePascal и могут быть проверены в любой среде, поддерживающей Паскаль.Выходные данные
soly
4
set
olymp
lye
too
chain.out
set
too
olymp
chain.in
solve
4
set
owe
evil
too
chain.out
?
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;
prev = 0 - нет предыдущего слова,
beetw или cpr - установим флаг цепочки в false (т.е. нет предшествующей цепочки),
pw = j - номер слова.
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;
