Задача A. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

В начале у игрока нулевой уровень усталости. Каждое перемещение добавляет к текущему уровню усталости единицу. Как только игрок перемещается на пиксель, занятый эликсиром, он выпивает эликсир, и уровень усталости уменьшается на единицу. Таким образом, перемещение на пиксель с эликсиром не увеличивает уровня усталости. Когда игрок покидает клетку, на которой был эликсир, она становится свободной.

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

Вам необходимо написать программу, которая по заданному плану коридора определит минимальный уровень усталости, с которым можно пройти игру.

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

В выходной файл выведите единственное число — минимальный уровень усталости, которого можно достичь, пройдя игру.

Ограничения

2 ≤ N ≤ 100

Примеры тестов

2
..
.#

1

6
....X.
#XXX..

3

Задача B. Чудик в Цветландии ≡

Условие

Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.

В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.

Цветы каждого региона в каждый из дней имеют определённую силу запаха, В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k−1) mod T.

Чудик очень любит нюхать цветы, поэтому он хочет выбрать свой маршрут путешествия по Цветландии так, чтобы как можно сильнее ощутить запах цветов.

Чудик выбирает, с какого региона он начнёт путешествие, и отправляется в путь. Путешествие Чудика длится K дней. За один день Чудик должен переместиться в соседний (сверху, справа, снизу или слева) регион.

В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k−1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.

Чудик хочет выбрать маршрут так, чтобы сумма сил запаха в регионах, через которые он пройдёт, была максимальной.

Комментарий к примеру

Силы запаха в регионах по дням:

0 0
0 0

1 1
1 1

0 0
2 0

1 1
0 1

Формат входного файла

Входной файл содержит целые числа N K. Далее следуют N² целых чисел T(x, y).

Формат выходного файла

Выходной файл должен содержать целое число — максимальную сумму сил запаха.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 100

2 ≤ T(x, y) ≤ 100

Примеры тестов

2 4
2 2
3 2

4

Задача C. Наибольшая общая подпоследовательность ≡

Условие

Найдите наибольшую общую подпоследовательность двух строк.

Формат входного файла

В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.

Формат выходного файла

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

Примеры тестов

ababaca
acaba

aaba