Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Код

Задачу добавил: alef

Успешно сдано решений: 6

На входной двери фирмы "Лето красное" установлен кодовый замок. Его всегда открывает директор фирмы, но сегодня он еще не добрался до работы из-за снегопада. Впрочем, это удалось и не всем сотрудникам фирмы.

Кодовый замок устроен следующим образом. Он состоит из M (3 <= M <= 26) вращающихся дисков, на каждом из которых (по окружности) написаны (по порядку, от A до Z) все буквы латинского алфавита. Диски можно поворачивать, выбранной считается буква, которая находится на позиции вверху. Когда буквы выбраны в нужной последовательности, замок открывается.

На двери каждого отдела также стоит кодовый замок, но из трех дисков. Сотрудники знают, что код каждого отдела является подпоследовательностью кода замка на входной двери (т.е. из кода замка на входной двери можно вычеркнуть M-3 символов таким образом, что оставшиеся образуют код отдела). Также известно, что в коде замка на входной двери ни одна буква не повторяется.

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

 

 

Формат входного файла input.txt

Первая строка – целые числа M и N через пробел (3 <= M <= 26, 1 <= N <= 100), M – количество дисков в кодовом замке, N – количество сотрудников, которым удалось добраться до работы.

Вторая строка - M заглавных латинских букв - текущая комбинация букв на кодовом замке

Каждая из следующих N строк содержит по три заглавных латинских буквы – коды отделов, известные добравшимся до работы сотрудникам.

 

Формат выходного файла output.txt

Первая строка - либо строка из M символов - код замка на входной двери, и через пробел - суммарное минимальное количество делений, на которое придется повернуть диски замка, чтобы получить эту строку, либо строка NO SOLUTION, если по входным данным невозможно найти код замка

 

Пример входного файла

4 2

SAAB

FIA

FAT

 

Пример выходного файла

FIAT 29

 

Сдать задачу

Задать вопрос жюри по этой задаче