АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

177. Скобки

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Рассмотрим множество S, состоящее из N (1 <= N <= 10) начальных букв латинского алфавита. Введём на этом множестве бинарную операцию умножения при помощи таблицы, т.е. каждой упорядоченной паре элементов из S поставим в соответствие некоторый элемент из S. Например, пусть = 2, тогда
S = {a, b}. Возьмём таблицу

 

a

b

a

b

a

b

b

b

Первая строка этой таблицы говорит о том, что a × a = b и a × b = a. Вторая строка означает, что b × a = b и b × b = b. Таким образом мы задали таблицу умножения для множества S.

В дальнейшем мы будем опускать символ умножения и вместо a × b будем писать просто ab. Умножение, заданное произвольной таблицей, не обязано быть ни коммутативно — ab не обязано равняться ba, ни ассоциативно — a(bc) не обязано равняться (ab)c.

Дано число N — количество элементов множества, таблица умножения для этого множества, строка, состоящая из маленьких латинских букв-элементов множества, а также задан некий элемент множества. Ваша программа должна расставить в данной строке скобки так, чтобы порядок умножения определялся однозначно, и результатом умножения был заданный элемент.

Время тестирования: 1 секунда на один тест на Intel Celeron 2500.

Первая строка входного файла содержит целое число N (1 <= N <= 10). Вторая строка содержит исходную строку из элементов множества. Гарантируется, что она будет содержать только разрешённые строчные латинские буквы, и её длина не превзойдёт 100. В третьей строке задан символ-элемент множества, который нужно получить в результате умножения. Следующие N строк содержат по N символов каждая — это таблица умножения. Символы в строках заданы без пробелов.

Если можно расставить скобки как требует того условие задачи, то в первой строке выходного файла выведите "YES", в противном случае — "NO" (большими буквами, без кавычек). В случае положительного ответа во второй строке выведите исходную строку с расставленными скобками. Скобки должны быть расставлены корректно, и длина ответа не должна превышать 500 символов. Если ответов несколько, выведите любой.

Примеры

STDIN

STDOUT

2
aabba
b
ba
bb
YES
(a(ab))(ba)
2
aabba
a
ba
bb
YES
(a((a(bb))a))

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / IX Межвузовская олимпиада 2006 /
176. F - Сообщение 177. 178. H - Транслятор
 
время генерации 0.141 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.