Вы можете зарегистрироваться и решать эту задачу здесь.
Ограничение времени: | 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 |
Видео разбор решения задачи здесь.