Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Во время ремонта новой квартиры Вам, как достаточно взрослым и ответственным людям, было поручено наклеить обои. На первый взгляд все выглядело достаточно просто, однако, когда Вы приступили к работе, обнаружилась небольшая проблема — необходимо выравнивать рисунок на соседних полосах обоев. Как настоящие программисты, Вы сформулировали задачу следующим образом.
Каждую полосу обоев можно описать ее частью — прямоугольником длины `N` и ширины `M` (чтобы получить полную полосу, этот прямоугольник можно много раз дорисовать к самому себе справа и слева). Для простоты мысленно поделим этот прямоугольник на равные ячейки так, чтобы получилось `N` строк и `M` столбцов. Чтобы было еще проще, рисунок на обоях обозначим символами '.' и '*' (точка и звездочка), по одному символу в каждой ячейке.
Вам дается описание двух полос обоев. Определите, на какое минимальное количество ячеек нужно сместить вторую полосу вправо, чтобы ее рисунок совпал с рисунком на первой полосе. Гарантируется, что это всегда можно сделать.
Первая строка входного файла содержит два целых числа `N` и `M` (`1\ ≤\ N\ ≤\ 20`, `1\ ≤\ M\ ≤\ 100000`), разделенных пробелом.
Следующие `N` строк содержат по `M` символов каждая — описание первой полосы обоев.
Следующие `N` строк содержат по `M` символов каждая — описание второй полосы обоев.
Каждая строка описания обоев состоит только из символов '.' и '*'.
В выходной файл выведите одно целое число — на какое минимальное количество ячеек нужно сместить вторую полосу вправо, чтобы ее рисунок совпал с рисунком на первой полосе.
Пример ввода 1
2 5
.*.*.
*.*.*
*.*..
.*.**
Пример ввода 2
1 5
***..
*..**
Источник: 3-й этап Республиканской олимпиады по информатике 2013, Казахстан