Интернет-банкинг — это современная технология, которая позволяет клиентам
банка получать доступ к информации о своих счетах с помощью сети Интернет из
практически любой точки земного шара. Разумеется, при использовании интернет-банкинга
большую роль играют вопросы безопасности. Поэтому для доступа к системе Интернет-банкинга
пользователю необходимо ввести пароль.
Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует
следующий способ ввода пароля. Серверной частью системы случайно генерируются
n строк s1, …, sn, каждая из которых состоит из m строчных букв латинского алфавита (предполагается,
что пароли состоят только из таких букв).
При вводе пароля пользователю разрешается
выполнять такую операцию: выбрать из данных строк две (обозначим их как si и sj, 1 ≤ i, j ≤ n, i ≠ j) и
некоторую позицию k (1 ≤ k ≤ m) в них, после чего поменять местами k-е символы в si и sj.
Например, если si=abcde, sj=vwxyz, k=3, то после выполнения этой операции
будут верны следующие равенства: si=abxde и sj=vwcyz. Для ввода пароля
пользователю необходимо за минимальное число таких операций добиться состояния,
в котором хотя бы одна из строк s1, …, sn совпадает с p.
Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк
s1, …, sn и паролю пользователя p определит минимальное число операций указанного типа,
которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за
такое число операций.
Формат входного файла
Первая строка входного файла содержит целое число n (2 ≤ n ≤ 100).
Каждая из последующих n строк содержит строки s1, …, sn. Все
они состоят только из строчных букв латинского алфавита и имеют одинаковую
длину m (2 ≤ m ≤ 100).
Последняя строка входного файла содержит пароль пользователя p. Его длина
равна m, и он состоит только из строчных букв латинского алфавита.
Формат выходного файла
Первая строка выходного файла должна содержать минимальное число c операций,
необходимых для ввода пароля. Если с помощью описанных в условии операций пароль
ввести нельзя, то выведите в первой строке −1.
В случае существования решения следующие c строк должны содержать описания операций.
Операции должны быть перечислены в порядке их применения, каждая из строк
должна содержать три целых числа: i, j и k (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m).
Эти числа означают, что соответствующая операция состоит в обмене k-ых символов строк
si и sj.
В последнее время фитнесс-клубы стали очень популярны среди жителей столицы Флатландии.
В такие клубы люди ходят после работы для того, чтобы поддерживать себя в хорошей физической форме.
В фитнесс-клубe "Флат" каждому из посетителей на время посещения выделяется один из k шкафчиков,
в который он может убрать свои вещи на время тренировки.
В течение дня в фитнесс-клубе проходит n тренировок, причем каждый из посетителей
приходит к началу какой-либо из этих тренировок (в этот момент он получает ключ от шкафчика)
и уходит сразу после ее окончания (в этот момент он сдает ключ от шкафчика). При этом
можно считать, что все посетители, закончившие тренировку, уходят раньше, чем все
посетители, пришедшие на следующую тренировку.
Некоторые из посетителей уходя закрывают шкафчик, а другие — не закрывают. Так как
все посетители фитнесс-клуба посещают его уже достаточно давно, то про каждого
из них персонал клуба знает, закроет ли он свой шкафчик, когда будет уходить.
Таким образом, для каждой тренировки известно два числа: число ai посетителей,
которые закроют шкафчик, и число bi посетителей, которые не закроют.
В начале дня все k шкафчиков закрыты. Разумеется, персоналу клуба хочется, чтобы в конце дня
также как можно больше шкафчиков были закрыты — тогда надо будет меньше работать при подготовке
к очередному дню. Для того, чтобы достичь этой цели, персонал может выдавать ключи от шкафчиков посетителям
произвольным образом. Например, имеет смысл выдавать ключ от открытого шкафчика тому, кто его точно закроет.
Необходимо найти максимальное число шкафчиков, которые окажутся закрытыми, в случае оптимальных
действий персонала фитнесс-клуба.
Формат входного файла
Первая строка входного файла содержит два целых числа: n (1 ≤ n ≤ 100) и k (1 ≤ k ≤ 1000). Каждая из
последующих n строк содержит по два целых числа ai и bi (0 ≤ ai, bi ≤ k, ai + bi ≤ k).
Формат выходного файла
В выходной файл выведите одно число — ответ на задачу.
Комментарий к примеру. Пронумеруем шкафчики числами от 1 до 4. Посетителям, пришедшим на первую тренировку выдадим ключи так:
тому, кто закроет, — от шкафчика 1, тем, кто не закроет, — от 2 и 3. Посетителям, пришедшим на вторую
тренировку, выдадим ключи так: тому, кто закроет, — номер 2, тому, кто не закроет, — номер 3. В итоге
открытым после окончания дня останется только шкафчик номер 3.
Джо — электрик-ковбой. Как у всех ковбоев у него есть лассо, как всем
электрикам ему иногда приходиться залезать на столбы, и как все он ленив.
Вот и сейчас ему поручили проверить два стоящих на расстоянии d друг от друга столба высоты h1 и h2 соответственно.
Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.
Электрик-ковбой посещает столбы следующим образом: сначала он выбирает один из столбов и просто взбирается на него.
Выполнив все работы на вершине,
он спускается по этому столбу на некоторую высоту (возможно до самой земли), достает свое лассо и цепляется им за
некоторую точку второго столба (это может быть произвольная точка).
После этого Джо прыгает и двигается вниз по дуге окружности с центром в точке, за которую зацепилось лассо,
пока не достигнет либо другого столба, либо земли.
При этом если от начальной позиции электрика до конца его полета высота изменяется более чем на l, то ковбой
набирает слишком большую скорость, больно ударяется и попадает в больницу, так и не выполнив работу.
Поэтому Джо всегда аккуратно выбирает параметры прыжка.
Если в результате прыжка Джо оказался
на земле, он подходит к другому столбу и взбирается на него. Если же Джо оказался на
столбе, то он взбирается на вершину из той точки, в которой он оказался.
Джо просит вас помочь ему выполнить работу, сообщив какое минимальное расстояние ему придется лезть
вверх по столбам.
Формат входного файла
Входной файл содержит четыре положительных целых числа: d, h1, h2 и l — расстояние между
столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно.
Все числа во входном файле не превышают 106.
Формат выходного файла
Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до~10−5.
В стране Лаккиландии очень развит общественный транспорт.
Проезд в нем бесплатный, но при этом каждому пассажиру при входе
выдают билетик с уникальным номером.
Особенно ценятся так называемые счастливые билетики.
Билетик называется счастливым, если сумма цифр на четных позициях в его номере
равна сумме цифр на нечетных позициях.
Ване известно, что билеты выдаются подряд в порядке возрастания номеров.
В очередной раз войдя в автобус Ваня получил свой очередной билет и тут ему стало интересно,
какой существует минимальный счастливый билетик с номером, большим номера Ваниного билетика.
Помогите Ване узнать ответ на этот вопрос.
Формат входного файла
В единственной строке входного файла задан номер Ваниного билетика — натуральное
число, имеющее в своей десятичной записи не более 100 цифр.
Формат выходного файла
В выходной файл выведите минимальный номер счастливого билетика, который
больше номера Ваниного билетика.
Палиндромом называется слово, которое читается одинаково в
обоих направлениях. Например, слово "шалаш" является палиндромом.
Для слова можно определить циклический сдвиг следующим образом:
часть букв из конца слова (возможно ни одной) переставляются в начало
с сохранением порядка относительно друг друга.
Например, слово "нора" является циклическим
сдвигом слова "рано" (надо перенести в начало буквы "но").
Будем называть слово циклическим палиндромом, если у него
есть циклический сдвиг, который является палиндромом. Например, слово
"масса" является циклическим палиндромом: его циклический сдвиг
"самас" является палиндромом.
Вам задано слово, состоящее не более чем из 100 букв латинского алфавита.
Требуется проверить, является ли это слово циклическим палиндромом.
Формат входного файла
Входной файл содержит одно слово, содержащее от 1 до 100 строчных букв
латинского алфавита.
Формат выходного файла
Если входной файл содержит циклический палиндром, выведите в выходной
файл слово "yes". В противном случае выведите "no".
В математике часто встречаются так называемые рекуррентные соотношения. Обычно
они применяются для задания числовых последовательностей — очередное число в последовательности
некоторым образом выражается через предыдущие. Примером такой последовательности
являются числа Фибоначчи (в них очередное число равно сумме двух предыдущих).
С помощью соотношений такого типа можно задавать не только последовательности
чисел, но и последовательности строк. В этой задаче рассматривается последовательность
строк s0, s1, …, задаваемая следующим образом.
Строка s0 пуста, а каждая строка
si (i ≥ 1) получается из si−1 по следующему правилу: если десятичная запись числа i
входит как подстрока в si−1, то si = si−1, иначе si получается приписыванием
к si−1 в конец десятичной записи числа i.
Задано число n. Необходимо найти строку sn.
Формат входного файла
Входной файл содержит целое число n (1 ≤ n ≤ 500).
