OCPC2021 E: Объясните теперь нам, вахтёры…

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени: 500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M

Объясните теперь нам, вахтёры…

В заведении «Покосившийся Скворечник» ЧП: на фоне ежеквартального обострения синдрома вахтёра из палаты номер 99 вырвался ночной сторож Михалыч и перегородил вход в уборную. Для пропуска внутрь он требует пароль, который он тут же записал на стене в виде строки из m строчных латинских символов. Но не всё так просто: недостаточно назвать пароль тщеславному Михалычу – нужно составить его из букв стихотворения, сочиненного ночным сторожем. И действительно, над паролем Михалыч записал стихи: n строк по m строчных латинских символов каждая. Чтобы получить искомый пароль, над ними разрешено проделывать следующую операцию: выбрать две различные строки с номерами i и j, выбрать номер символа k, а затем поменять местами k-й символ в строках номер i и j. Например, если мы меняем 3-й символ в паре строк «abcde» и «fghij», то получим «abhde» и «fgcij». Так нужно делать до тех пор, пока одна из строк не совпадёт с паролем.

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

Первая строка ввода содержит целое число n (2 ≤ n ≤ 100) – количество строк в стихотворении Михалыча. Каждая из последующих n строк состоит из строчных латинских символов и имеет одинаковую длину m (2 ≤ m ≤ 100). Последняя строка содержит пароль Михалыча длины m.

Первая строка вывода должна содержать минимальное число x операций над строками. Если получить пароль никак невозможно, выведите -1. В следующих x строках, если возможно получить пароль, выведите последовательность операций в формате i j k – номера первой и второй строк стихотворения Михалыча, над которыми производится операция обмена и номер символа в этих строках.

Примеры

Входные данные Результат работы
3
cab
abc
bca
cba
2
1 3 3
1 2 2
3
dbc
aeb
cca
acd
-1

Видео разбор решения задачи здесь.

Related Images:

Добавить комментарий