|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ.
Сложность Дельта
Рассмотрим множество S, состоящее из N (1 ≤ N ≤ 10)
начальных букв латинского алфавита. Введём на этом множестве бинарную операцию
умножения при помощи таблицы, т.е. каждой упорядоченной паре элементов из
S поставим в соответствие некоторый элемент из S. Например, пусть N = 2,
тогда S = {a, b}. Возьмём таблицу
Первая строка этой таблицы говорит о том, что a · a = b и
a · b = a. Вторая строка означает, что
b · a = b и b · b = b. Таким образом
мы задали таблицу умножения для множества S. В дальнейшем мы будем опускать
символ умножения и вместо a · b будем писать просто ab. Умножение,
заданное произвольной таблицей, не обязано быть ни коммутативно: ab не
обязано равняться ba, ни ассоциативно: a(bc) не обязано равняться (ab)c.
Дано число N - количество элементов множества, таблица умножения для
этого множества, строка, состоящая из маленьких латинских букв-элементов
множества, а также задан некий элемент множества. Ваша программа должна
расставить в данной строке скобки так, чтобы порядок умножения определялся
однозначно, и результатом умножения был заданный элемент.
Ввод
Первая строка ввода содержит целое число N (1 ≤ N ≤ 10).
Вторая строка содержит исходную строку из элементов множества. Гарантируется,
что она будет содержать только разрешённые строчные латинские буквы, и её
длина не превзойдёт 100. В третьей строке задан символ-элемент множества,
который нужно получить в результате умножения. Следующие N строк
содержат по N символов каждая - это таблица умножения. Символы в
строках заданы без пробелов.
Вывод
Если можно расставить скобки как требует того условие задачи, то в первой
строке вывода выведите "YES", в противном случае - "NO"
(большими буквами, без кавычек). В случае положительного ответа во второй
строке выведите исходную строку с расставленными скобками. Скобки должны быть
расставлены корректно, и длина ответа не должна превышать 500 символов.
Если ответов несколько, выведите любой.
|
Ввод 1
|
Ввод 2
|
2
aabba
b
ba
bb
|
2
aabba
a
ba
bb
|
|
Вывод 1
|
Вывод 2
|
YES
(a(ab))(ba)
|
YES
(a((a(bb))a))
|
Для отправки решений необходимо выполнить вход.
|