printРабочее место участника

printЗадачи

1924. Поклейка обоев

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Во время ремонта новой квартиры Вам, как достаточно взрослым и ответственным людям, было поручено наклеить обои. На первый взгляд все выглядело достаточно просто, однако, когда Вы приступили к работе, обнаружилась небольшая проблема — необходимо выравнивать рисунок на соседних полосах обоев. Как настоящие программисты, Вы сформулировали задачу следующим образом.
Каждую полосу обоев можно описать ее частью — прямоугольником длины `N` и ширины `M` (чтобы получить полную полосу, этот прямоугольник можно много раз дорисовать к самому себе справа и слева). Для простоты мысленно поделим этот прямоугольник на равные ячейки так, чтобы получилось `N` строк и `M` столбцов. Чтобы было еще проще, рисунок на обоях обозначим символами '.' и '*' (точка и звездочка), по одному символу в каждой ячейке.
Вам дается описание двух полос обоев. Определите, на какое минимальное количество ячеек нужно сместить вторую полосу вправо, чтобы ее рисунок совпал с рисунком на первой полосе. Гарантируется, что это всегда можно сделать.
Первая строка входного файла содержит два целых числа `N` и `M` (`1\ ≤\ N\ ≤\ 20`, `1\ ≤\ M\ ≤\ 100000`), разделенных пробелом. Следующие `N` строк содержат по `M` символов каждая — описание первой полосы обоев. Следующие `N` строк содержат по `M` символов каждая — описание второй полосы обоев. Каждая строка описания обоев состоит только из символов '.' и '*'.
В выходной файл выведите одно целое число — на какое минимальное количество ячеек нужно сместить вторую полосу вправо, чтобы ее рисунок совпал с рисунком на первой полосе.

Пример ввода 1

2 5
.*.*.
*.*.*
*.*..
.*.**

Пример вывода 1

1

Пример ввода 2

1 5
***..
*..**

Пример вывода 2

2
Источник: 3-й этап Республиканской олимпиады по информатике 2013, Казахстан
loading