Из гвардейцев в мушкетёры

Из гвардейцев в мушкетёры

Условия задачи

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

Кардинал отнюдь не пришёл в восторг, но ослушаться королевского приказа он не мог. С другой стороны, он не был бы кардиналом, если бы не сумел придумать по этому случаю какую-нибудь небольшую каверзу.

Вызвав к себе виновников происшествия (их было шестеро), он приказал им следующее: явиться к капитану мушкетёров, но не представляться ему, а вручить кардинальское письмо и построиться по росту. Бывшие гвардейцы в точности исполнили приказ.

Распечатав письмо, капитан мушкетёров прочёл:

«В строю E стоит где-то слева от B. Справа от A в строю нет F. Где-то слева от D стоит C. Вторую позицию занимает A. E и D стоят в строю подряд друг за другом. Вот ваше пополнение, господин капитан, а кто из них кто — извольте разбираться сами!»

(Разумеется, вместо букв A,B,C,D,E,F в кардинальском письме были указаны настоящие имена и титулы, но для нас они за давностью лет совершенно не важны.)

Мысленно выругав кардинала и поразмыслив некоторое время, капитан всё же догадался, что бывшие гвардейцы стоят перед ним в следующем порядке: F,A,C,E,D,B.

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

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

В первой строке файла два числа: количество гвардейцев n и число условий расстановки k. В каждой из последующих k строк записано по одному условию. Условия кодируются следующим образом:

Запись «E<B» означает «E стоит левее B» (при этом между ними может стоять кто-то ещё). Аналогично, «C<D» означает, «C стоит левее D».

Запись «A<f» означает «справа от A в строю нету F» (обратите внимание, что в данном случае используется символ не «F», а «f». Аналогично, запись «a<F», означала бы «слева от F в строю нету A»).

Запись «A=2» означает «A стоит в строю вторым».

Запись «E, D» означает «E и D стоят в строю подряд: сначала E, потом D».

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

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

В первой строке файла должны быть записаны первые n букв латинского алфавита в верхнем регистре. Порядок записи соответствует порядку расстановки гвардейцев в строю.

Тестовый пример

Вход:

6 5

E<B

A<f

C<D

A=2

E, D

Выход:

FACEDB

Столкновение с реальностью номер один

В таком виде эта задача была мной предложена оргкомитету олимпиады. Оргкомитет задачу принял, однако мне было сказано, что её условия скорее всего изменят в сторону, упрощающую тестирование. После чего я (не зная смысла грядущих изменений) не увидел смысла изображать своё обсуждение и решение. Однако выяснилось, что на олимпиаду задача была выставлена всё же в своём первозданном виде. Посему ниже предлагается разбираемый на примере алгоритм, а писать полное обсуждение и решение мне было уже лениво. J

Алгоритм

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

1)  Правила вида «X=номер» выполнить немедленно и исключить из списка правил.

2)  Правила вида «X>y» и «x<Y» преобразовать в «Y<X».

3)  Правила вида «X>Y» преобразовать в «Y<X».

4)  Правила вида «X, Y», в которых присутствуют уже расставленные имена, выполнить немедленно.

5)  По всем правилам вида «X, Y» построить объединённые имена типа «XY» и соответственно преобразовать связанные с ними правила.

6)  Исключить повторяющиеся правила.

7)  Исключить правила, связанные с именами, которые уже расставлены подряд в самом начале и самом конце.

8)  Исключить правила, связанные с уже расставленными именами, присутствующими только слева или только справа.

9)  Построить по оставшимся правилам ориентированный граф с вершинами-именами.

10)  Найти в графе путь, проходящий через все вершины.

11)  Расставить ещё не расставленные имена по свободным позициям в порядке, определяемом найденным на предыдущем шаге путём.

Теперь разберём этот алгоритм на примере следующего теста с восемью именами и десятью правилами:

F=5 E, B A<E C<F B<F D, H C<D H<G C>a c<B

Шаг №1 приводит к расстановке ****F*** и сокращает набор правил:

E, B A<E C<F B<F D, H C<D H<G C>a c<B

Шаг №2 меняет два последних правила:

E, B A<E C<F B<F D, H C<D H<G A<C B<C

Шаг №3 в данном случае ничего не меняет.

Шаг №4 также ничего не меняет: расставлено только одно имя «F», которого нет в правилах «E, B» и «D, H».

Шаг №5 приводит к формированию объединённых имен «EB» и «DH». Набор правил преобразуется следующим образом:

A<EB C<F EB<F C<DH DH<G A<C EB<C

Шаг №6 ничего не меняет: повторяющихся правил здесь нет.

Шаг №7 ничего не меняет: в начале и конце нет расставленных подряд имён.

Шаг №8 приводит к исключению второго и третьего правил: в них уже расставленное имя «F» присутствует только справа:

A<EB C<DH DH<G A<C EB<C

Шаг №9 даёт нам следующий ориентированный граф с пять вершинами, соответствующими пяти оставшимся именам A, EB, C, DH, G:

На шаге №10 находим в графе следующий путь: A ® EB ® C ® DH ® G.

Шаг №11 сводится к расстановке в еще не занятые позиции свободных имён в порядке A, E,B, C,D, H,G. Получаем ответ к задаче: AEBCFDHG.

Столкновение с реальностью номер два

Задача была предложена не региональном четвертьфинале АСМ (ноябрь 2006), в котором участвовали 74 команды. Решать её пытались 11 команд, и четырём командам это удалось (в том числе одна команда сдала задачу сразу, с первой же попытки). Остальные семь команд решить задачу не смогли. В целом всё это вполне соответствует довольно сложному уровню задачи.